अनुक्रम संरेखण एल्गोरिदम
अनुक्रम संरेखण एल्गोरिदम प्रविष्टि, विलोपन और प्रतिस्थापन पर गतिशील प्रोग्रामिंग का उपयोग करके, एक स्ट्रिंग को दूसरे में बदलने के सबसे कम लागत वाले तरीके को खोजकर दो स्ट्रिंग के बीच समानता को मापते और प्रदर्शित करते हैं।
Definition
अनुक्रम संरेखण दो (या अधिक) स्ट्रिंग की व्यवस्था है ताकि अंतराल डालकर और वर्णों का मिलान, बेमेल या प्रतिस्थापन करके उनके पत्राचार को अधिकतम किया जा सके; एक संरेखण एल्गोरिदम आमतौर पर गतिशील प्रोग्रामिंग के माध्यम से एक दिए गए लागत या स्कोरिंग मॉडल के तहत एक इष्टतम संरेखण और उसके स्कोर की गणना करता है।
Scope
यह विषय स्ट्रिंग की तुलना करने के लिए गतिशील-प्रोग्रामिंग एल्गोरिदम को शामिल करता है: संपादन (लेवेनस्टीन) दूरी और सबसे लंबी सामान्य उप-अनुक्रम, वैश्विक संरेखण (नीडलमैन-वुन्श), स्थानीय संरेखण (स्मिथ-वॉटरमैन), और स्कोरिंग योजनाएं (गैप पेनल्टी, प्रतिस्थापन मैट्रिक्स) जो जैविक संरेखण को आकार देती हैं। यह अंतर्निहित पुनरावृत्ति और इसकी द्विघात समय और स्थान लागत, साथ ही स्थान-बचत परिष्करण का इलाज करता है। अनुक्रमणिका-आधारित और सटीक-मिलान विधियों को संबंधित विषयों में शामिल किया गया है।
Core questions
- दो स्ट्रिंग के बीच समानता को संपादन दूरी या संरेखण स्कोर के रूप में कैसे मापा जाता है?
- एक गतिशील-प्रोग्रामिंग तालिका एक इष्टतम संरेखण की गणना कैसे करती है?
- वैश्विक संरेखण को स्थानीय संरेखण से क्या अलग करता है, और प्रत्येक कब उपयुक्त होता है?
- गैप पेनल्टी और प्रतिस्थापन मैट्रिक्स परिणामी संरेखण को कैसे प्रभावित करते हैं?
- लंबी अनुक्रमों के लिए द्विघात स्थान की आवश्यकता को कैसे कम किया जा सकता है?
Key concepts
- संपादन (लेवेनस्टीन) दूरी
- सबसे लंबी सामान्य उप-अनुक्रम
- वैश्विक संरेखण
- स्थानीय संरेखण
- नीडलमैन-वुन्श एल्गोरिदम
- स्मिथ-वॉटरमैन एल्गोरिदम
- गैप पेनल्टी
- प्रतिस्थापन मैट्रिक्स
Key theories
- गतिशील प्रोग्रामिंग द्वारा वैश्विक संरेखण
- नीडलमैन-वुन्श एल्गोरिदम एक गतिशील-प्रोग्रामिंग तालिका को भरता है जिसकी प्रविष्टियाँ स्ट्रिंग उपसर्गों के सर्वोत्तम संरेखण स्कोर देती हैं, जिससे उनकी लंबाई के गुणनफल के अनुपात में समय में दो अनुक्रमों का एक इष्टतम एंड-टू-एंड (वैश्विक) संरेखण प्राप्त होता है।
- साझा उप-अनुक्रमों के लिए स्थानीय संरेखण
- स्मिथ-वॉटरमैन एल्गोरिदम पुनरावृत्ति को संशोधित करता है ताकि संरेखण कहीं भी शुरू और समाप्त हो सके, उच्चतम-स्कोरिंग मिलान क्षेत्र (स्थानीय संरेखण) को ढूंढता है, जो अन्यथा भिन्न अनुक्रमों के भीतर संरक्षित खंडों का पता लगाने के लिए आवश्यक है।
Clinical relevance
अनुक्रम संरेखण कम्प्यूटेशनल जीव विज्ञान का एक आधार है, जिसका उपयोग समरूपता, विकासवादी अनुमान और डेटाबेस खोज के लिए डीएनए, आरएनए और प्रोटीन अनुक्रमों की तुलना करने के लिए किया जाता है (अनुमानी BLAST स्थानीय संरेखण पर आधारित है)। जीव विज्ञान के बाहर, वही संपादन-दूरी मशीनरी वर्तनी जांच, अस्पष्ट पाठ मिलान, संस्करण-नियंत्रण अंतर, और भाषण और हस्तलेखन तुलना को शक्ति प्रदान करती है।
History
लेवेनस्टीन ने 1965 में संपादन दूरी की शुरुआत की। नीडलमैन और वुन्श ने 1970 में प्रोटीन के लिए पहला गतिशील-प्रोग्रामिंग वैश्विक-संरेखण एल्गोरिदम दिया, और स्मिथ और वॉटरमैन ने 1981 में स्थानीय संरेखण की शुरुआत की। हिर्शबर्ग की रैखिक-स्थान तकनीक (1975) और बाद में BLAST जैसे अनुमानों ने संरेखण को बड़े पैमाने पर व्यावहारिक उपयोग तक बढ़ाया।
Key figures
- Saul Needleman
- Christian Wunsch
- Temple Smith
- Michael Waterman
- Vladimir Levenshtein
Related topics
Seminal works
- needleman1970
- smith1981
- gusfield1997
Frequently asked questions
- वैश्विक और स्थानीय संरेखण में क्या अंतर है?
- वैश्विक संरेखण (नीडलमैन-वुन्श) दो अनुक्रमों को एंड-टू-एंड संरेखित करता है और उपयुक्त होता है जब वे समान लंबाई के होते हैं और पूरे में संबंधित होने की उम्मीद होती है। स्थानीय संरेखण (स्मिथ-वॉटरमैन) सबसे अच्छा-मिलान करने वाला उपक्षेत्र ढूंढता है और उपयुक्त होता है जब अनुक्रमों के केवल कुछ हिस्से समान होते हैं, जैसे बड़े अनुक्रमों के भीतर एक संरक्षित डोमेन।
- क्या अनुक्रम संरेखण सबसे लंबी सामान्य उप-अनुक्रम के समान है?
- वे निकटता से संबंधित हैं। सबसे लंबी सामान्य उप-अनुक्रम विशेष स्कोरिंग (मिलान को पुरस्कृत किया जाता है, अंतराल मुक्त होते हैं, बेमेल की अनुमति नहीं होती है) के साथ संरेखण का एक विशेष मामला है। सामान्य संरेखण प्रतिस्थापन लागत और गैप पेनल्टी के साथ समृद्ध स्कोरिंग का उपयोग करता है, लेकिन दोनों को एक ही प्रकार की गतिशील-प्रोग्रामिंग पुनरावृत्ति द्वारा हल किया जाता है।