एक बड़े डेटाबेस में (बहुत) अनुमानित सबस्ट्रिंग्स खोजें

Question

मैं बड़े डेटाबेस में लंबे, अनुमानित सबस्ट्रिंग खोजने की कोशिश कर रहा हूं। उदाहरण के लिए, एक क्वेरी 1000 वर्ण सबस्ट्रिंग हो सकती है जो कई सौ संपादनों की लेवेनशेटिन दूरी से मैच से भिन्न हो सकती है। मैंने सुना है कि अनुक्रमित क्यू-ग्राम ऐसा कर सकते हैं, लेकिन मुझे कार्यान्वयन के विवरण नहीं पता हैं। मैंने यह भी सुना है कि लुसीन ऐसा कर सकता है, लेकिन ल्यूसीन का लेवेनशेटिन एल्गोरिदम सैकड़ों संपादन के लिए पर्याप्त तेज़ है? शायद चोरी चोरी की दुनिया से बाहर कुछ? किसी भी सलाह की सराहना की है।

Answer 1

क्यू ग्राम एक दृष्टिकोण हो सकता है, लेकिन ऐसी ब्लास्ट, BlastP के रूप में दूसरों रहे हैं - जो प्रोटीन के लिए उपयोग किया जाता है, न्यूक्लियोटाइड मैचों आदि

Simmetrics पुस्तकालय स्ट्रिंग दूरी दृष्टिकोण की एक व्यापक संग्रह है।

Answer 2

लुसीन यहां सही उपकरण प्रतीत नहीं होता है। मिकोस के अच्छे सुझावों के अलावा, मैंने AGREP, FASTA और Locality-Sensitive Hashing(LSH) के बारे में सुना है। मेरा मानना ​​है कि एक कुशल विधि को पहले खोज स्थान को भारी रूप से छीनना चाहिए, और उसके बाद शेष उम्मीदवारों पर अधिक परिष्कृत स्कोरिंग करना चाहिए।