ठीक है, सुईमेन-वुन्श (एनडब्ल्यू) बायोइनफॉरमैटिक्स साहित्य से क्लासिक एंड-टू-एंड ("ग्लोबल") संरेखक है। यह बहुत पहले FASTA पैकेज में "संरेखण" और "align0" के रूप में उपलब्ध था। अंतर यह था कि "0" संस्करण एंड-गैपिंग से बचने के पक्षपातपूर्ण नहीं था, जो अक्सर उच्च गुणवत्ता वाले आंतरिक मैचों को आसान बनाने की अनुमति देता था। स्मिथ-वाटमैन, मुझे संदेह है कि आप जानते हैं, एक स्थानीय संरेखक है और यह ब्लास्ट का मूल आधार है। फास्टा का अपना स्थानीय संरेखक था और साथ ही यह थोड़ा अलग था। ये सभी अनिवार्य रूप से ह्यूरिस्टिक विधियों का आकलन करने के लिए अलग-अलग चरित्र जोड़े (बायोइनफॉरमैटिक्स में, अक्सर डेहॉफ/"पीएएम", हेनिकोफ & हेनिकोफ, या अन्य मैट्रिस के लिए स्कोरिंग मीट्रिक से संबंधित लेवेनशेटिन दूरी का आकलन करने के लिए अनिवार्य रूप से प्रभावी तरीके हैं और आमतौर पर कुछ सरल और अधिक उचित रूप से प्रतिबिंबित होते हैं प्राकृतिक भाषा पर लागू होने पर भाषाई शब्द रूपरेखा में प्रतिस्थापन के)।
चलिए लेबल के बारे में अनमोल नहीं हैं: कम से कम अभ्यास में संदर्भित लेवेनशेटिन दूरी मूल रूप से दूरी संपादित करती है और आपको इसका अनुमान लगाना पड़ता है क्योंकि आम तौर पर इसकी गणना करना संभव नहीं है, और यह वास्तव में दिलचस्प विशेष में भी गणना करना महंगा है मामले: पानी वहां तेजी से गहरा हो जाता है, और इस प्रकार हमारे पास लंबे और अच्छे प्रतिष्ठा के उत्थानवादी तरीके हैं।
अब अपनी समस्या के रूप में: कई साल पहले, मुझे संदर्भ अनुक्रम के खिलाफ छोटे डीएनए पढ़ने की सटीकता की जांच करनी थी जिसे सही कहा जाता था और मैं कुछ "एन्चर्ड संरेखण" कहलाता था।
विचार है कि आपका संदर्भ स्ट्रिंग सेट लेना और उन सभी स्थानों को ढूंढकर "पचाना" जहां एक दिया गया एन-वर्ण सबस्ट्रिंग होता है। एन चुनें ताकि आपके द्वारा बनाई गई तालिका बहुत बड़ी न हो, बल्कि यह भी कि लंबाई एन के सबस्ट्रिंग बहुत आम नहीं हैं। डीएनए बेस जैसे छोटे अक्षरों के लिए, एन अक्षरों के तारों पर एक परिपूर्ण हैश के साथ आना संभव है और प्रत्येक बिन से एक लिंक्ड सूची में एक टेबल बनाते हैं और मैचों को चेन करते हैं। सूची प्रविष्टियों को अनुक्रम की पहचान करना चाहिए और उस सबस्ट्रिंग की स्थिति शुरू करना चाहिए जो बिन को मानचित्र करता है जिसमें उनकी सूची होती है। यह खोज की जाने वाली तारों की सूची में "एंकर" हैं, जिन पर एक एनडब्ल्यू संरेखण उपयोगी होने की संभावना है।
क्वेरी स्ट्रिंग को संसाधित करते समय, आप एन स्ट्रिंग को क्वेरी स्ट्रिंग में कुछ ऑफसेट के शुरू में लेते हैं, हैश उन्हें, उनके बिन को देखते हैं, और यदि उस बिन की सूची अपर्याप्त है तो आप सभी सूची रिकॉर्ड्स से गुजरते हैं और क्वेरी स्ट्रिंग और रिकॉर्ड में संदर्भित खोज स्ट्रिंग के बीच संरेखण निष्पादित करें। इन संरेखणों को करते समय, आप क्वेरी स्ट्रिंग और खोज स्ट्रिंग को एंकर पर खोजते हैं और खोज स्ट्रिंग का एक सबस्ट्रिंग निकालें जो क्वेरी स्ट्रिंग के समान लंबाई है और जिसमें उसी ऑफसेट पर एंकर होता है, के।
यदि आप लंबे समय तक एंकर लंबाई एन चुनते हैं, और ऑफ़सेट के मूल्यों का एक उचित सेट (उन्हें क्वेरी स्ट्रिंग में फैलाया जा सकता है या कम ऑफसेट तक सीमित किया जा सकता है) तो आपको संभावित संरेखण का सबसेट मिलना चाहिए और अक्सर प्राप्त होगा स्पष्ट विजेता आम तौर पर आप कम अंत-पक्षपातपूर्ण align0- जैसे एनडब्ल्यू संरेखक का उपयोग करना चाहते हैं।
यह विधि एनडब्ल्यू को अपने इनपुट को प्रतिबंधित करके थोड़ा सा बढ़ावा देने की कोशिश करती है और इसका प्रदर्शन लाभ होता है क्योंकि आप कम संरेखण करते हैं और वे अक्सर समान अनुक्रमों के बीच होते हैं। आपके एनडब्लू संरेखक के साथ एक और अच्छी बात यह है कि लागत को कम करने के लिए कुछ मात्रा या गैपिंग की लंबाई होने के बाद इसे छोड़ने की अनुमति दी जाती है, खासकर यदि आप जानते हैं कि आप मिडलिंग-क्वालिटी मैचों में दिलचस्पी नहीं ले रहे हैं या रुचि रखते हैं।
आखिरकार, इस विधि का उपयोग छोटे अक्षरों वाले सिस्टम पर किया गया था, के साथ क्वेरी स्ट्रिंग में पहले 100 या ऐसे पदों तक सीमित था और क्वेरी स्ट्रिंग्स क्वेरी के मुकाबले बहुत बड़ी थीं (डीएनए पढ़ने लगभग 1000 आधार थे और सर्च स्ट्रिंग 10000 के क्रम में थीं, इसलिए मैं विशेष रूप से संपादन दूरी के अनुमान के आधार पर अनुमानित सबस्ट्रिंग मैचों की तलाश कर रहा था)। इस पद्धति को प्राकृतिक भाषा में अपनाने के लिए कुछ सावधानीपूर्वक विचार की आवश्यकता होगी: आप वर्णमाला आकार पर हार जाते हैं, लेकिन यदि आपकी क्वेरी स्ट्रिंग्स और सर्च स्ट्रिंग समान लंबाई के हैं तो आप लाभ प्राप्त करते हैं।
किसी भी तरह से, क्वेरी स्ट्रिंग के विभिन्न सिरों से एक से अधिक एंकर को एक साथ उपयोग करने की इजाजत देने के लिए एनडब्लू को खिलाए गए डेटा को आगे फ़िल्टर करने में सहायक हो सकता है। यदि आप ऐसा करते हैं, तो संभावित रूप से ओवरलैपिंग स्ट्रिंग्स को भेजने के लिए तैयार रहें, जिनमें से प्रत्येक को दो एंकरों में से एक को संरेखक में भेज दिया जाए और उसके बाद संरेखण को दोबारा जोड़ दें ... या संभावित रूप से आगे बढ़ने के लिए एनडब्लू को संशोधित करें ताकि आपके एंकरों को अधिकतर संरेखण के दौरान दंड संशोधन के दौरान संरेखण के दौरान बरकरार रखा जा सके। एल्गोरिदम का निष्पादन।
आशा है कि यह सहायक या कम से कम दिलचस्प है।
क्या आप 'वास्तविक' तार (यानी, अंग्रेजी) या जैव सूचना विज्ञान से मेल खाते हैं? यदि वास्तविक तार, आप अपने प्रतिस्थापन मैट्रिक्स के लिए क्या उपयोग कर रहे हैं? –
यहां इसी तरह के प्रश्न http://stackoverflow.com/questions/31494/how-to-detect-duplicate- डेटा और यहां http://stackoverflow.com/questions/42013/levenshtein-distance-based-methods-vs-उंडएक्स अन्य संबंधित टैग और खोज शब्दों के माध्यम से मिल सकते हैं। हालांकि, आपने बिल्कुल निर्दिष्ट नहीं किया * क्यों * आपको तारों से मिलान करने की आवश्यकता है - क्या आप डुप्लिकेट डेटा की जांच कर रहे हैं? –