Smith–Waterman algorithm
स्मिथ-वाटरमैन एल्गोरिथ्म स्थानीय अनुक्रम संरेखण करता है; अर्थात, न्यूक्लिक एसिड अनुक्रमों या प्रोटीन अनुक्रमों के दो तारों के बीच समान क्षेत्रों का निर्धारण करने के लिए। पूरे अनुक्रम को देखने के बजाय, स्मिथ-वाटरमैन एल्गोरिथ्म सभी संभावित लंबाई के खंडों की तुलना करता है और समानता माप को अनुकूलित करता है। एल्गोरिथम को पहली बार 1981 में टेम्पल एफ. स्मिथ और माइकल एस. वाटरमैन द्वारा प्रस्तावित किया गया था। नीडलमैन-वुन्श एल्गोरिदम की तरह, जिसमें से यह एक भिन्नता है, स्मिथ-वाटरमैन एक गतिशील प्रोग्रामिंग एल्गोरिदम है। इस प्रकार, इसमें वांछनीय गुण है कि उपयोग की जा रही स्कोरिंग प्रणाली (जिसमें प्रतिस्थापन मैट्रिक्स और अंतराल-स्कोरिंग योजना शामिल है) के संबंध में इष्टतम स्थानीय संरेखण खोजने की गारंटी है। नीडलमैन-वुन्श एल्गोरिथम में मुख्य अंतर यह है कि नकारात्मक स्कोरिंग मैट्रिक्स कोशिकाओं को शून्य पर सेट किया जाता है, जो (इस प्रकार सकारात्मक स्कोरिंग) स्थानीय संरेखण को दिखाई देता है। ट्रेसबैक प्रक्रिया उच्चतम स्कोरिंग मैट्रिक्स सेल से शुरू होती है और तब तक आगे बढ़ती है जब तक कि शून्य स्कोर वाली सेल का सामना नहीं किया जाता है, जिससे उच्चतम स्कोरिंग स्थानीय संरेखण प्राप्त होता है। इसकी घन समय जटिलता के कारण, इसे अक्सर बड़े पैमाने पर समस्याओं पर व्यावहारिक रूप से लागू नहीं किया जा सकता है और कम्प्यूटेशनल रूप से अधिक कुशल विकल्पों जैसे (गोटोह, 1982), (आल्ट्सचुल और एरिकसन, 1986), और (मायर्स और मिलर, 1988) के पक्ष में प्रतिस्थापित किया जाता है। 1970 में, शाऊल बी. नीडलमैन और क्रिश्चियन डी. वुन्श ने अनुक्रम संरेखण के लिए एक ह्यूरिस्टिक होमोलॉजी एल्गोरिथ्म का प्रस्ताव रखा, जिसे नीडलमैन-वुन्श एल्गोरिथ्म भी कहा जाता है। यह एक वैश्विक संरेखण एल्गोरिथ्म है जिसके लिए गणना चरणों की आवश्यकता होती है (और दो अनुक्रमों की लंबाई संरेखित की जा रही है)। यह वैश्विक संरेखण दिखाने के उद्देश्य से एक मैट्रिक्स की पुनरावृत्ति गणना का उपयोग करता है। अगले दशक में, सैंकॉफ, रीचार्ट, बेयर और अन्य लोगों ने जीन अनुक्रमों का विश्लेषण करने के लिए वैकल्पिक ह्यूरिस्टिक एल्गोरिदम तैयार किए। विक्रेताओं ने अनुक्रम दूरी को मापने के लिए एक प्रणाली शुरू की। 1976 में, वाटरमैन एट अल। मूल मापन प्रणाली में अंतराल की अवधारणा को जोड़ा गया। 1981 में, स्मिथ और वाटरमैन ने स्थानीय संरेखण की गणना के लिए अपने स्मिथ-वाटरमैन एल्गोरिदम को प्रकाशित किया। स्मिथ-वाटरमैन एल्गोरिदम समय की काफी मांग करता हैः लंबाई और समय के दो अनुक्रमों को संरेखित करने के लिए समय की आवश्यकता होती है। गोटोह और आल्ट्सचुल ने एल्गोरिथ्म को चरणों के लिए अनुकूलित किया। स्थान जटिलता को मायर्स और मिलर द्वारा (रैखिक) से अनुकूलित किया गया था, जहां छोटे अनुक्रम की लंबाई है, उस मामले के लिए जहां कई संभावित इष्टतम संरेखणों में से केवल एक वांछित है। चौधरी, ले और रामचंद्रन ने बाद में इनपुट अनुक्रमों की कुल लंबाई में स्थान उपयोग को रैखिक रखते हुए एल्गोरिथ्म के कैश प्रदर्शन को अनुकूलित किया। प्रेरणा हाल के वर्षों में, विभिन्न जीवों पर आयोजित जीनोम परियोजनाओं ने जीन और प्रोटीन के लिए भारी मात्रा में अनुक्रम डेटा उत्पन्न किया, जिसके लिए कम्प्यूटेशनल विश्लेषण की आवश्यकता होती है। अनुक्रम संरेखण जीन के बीच या प्रोटीन के बीच संबंधों को दर्शाता है, जिससे उनकी समरूपता और कार्यक्षमता की बेहतर समझ होती है। अनुक्रम संरेखण संरक्षित डोमेन और रूपांकनों को भी प्रकट कर सकता है। स्थानीय संरेखण के लिए एक प्रेरणा दूर से संबंधित जैविक अनुक्रमों के बीच कम समानता वाले क्षेत्रों में सही संरेखण प्राप्त करने में कठिनाई है, क्योंकि उत्परिवर्तन ने उन क्षेत्रों की सार्थक तुलना की अनुमति देने के लिए विकासवादी समय पर बहुत अधिक 'शोर' जोड़ा है। स्थानीय संरेखण ऐसे क्षेत्रों से पूरी तरह से बचाता है और सकारात्मक अंक वाले क्षेत्रों पर ध्यान केंद्रित करता है। जिनके पास समानता का एक विकासवादी रूप से संरक्षित संकेत है। स्थानीय संरेखण के लिए एक पूर्व शर्त एक नकारात्मक अपेक्षा अंक है। प्रत्याशित अंक को उस औसत अंक के रूप में परिभाषित किया जाता है जो अंक प्रणाली (प्रतिस्थापन मैट्रिक्स और अंतराल दंड) एक यादृच्छिक अनुक्रम के लिए देगा। स्थानीय संरेखण का उपयोग करने के लिए एक अन्य प्रेरणा यह है कि इष्टतम स्थानीय संरेखण के लिए एक विश्वसनीय सांख्यिकीय मॉडल (कार्लिन और आल्ट्सचुल द्वारा विकसित) है। असंबंधित अनुक्रमों का संरेखण इष्टतम स्थानीय संरेखण स्कोर का उत्पादन करता है जो एक चरम मूल्य वितरण का पालन करता है। यह गुण कार्यक्रमों को दो अनुक्रमों के इष्टतम स्थानीय संरेखण के लिए एक अपेक्षा मूल्य का उत्पादन करने की अनुमति देता है, जो इस बात का एक उपाय है कि कितनी बार दो असंबंधित अनुक्रम एक इष्टतम स्थानीय संरेखण का उत्पादन करेंगे जिसका स्कोर देखे गए स्कोर से अधिक या उसके बराबर है। बहुत कम अपेक्षा मूल्य इंगित करते हैं कि विचाराधीन दो अनुक्रम समरूप हो सकते हैं, जिसका अर्थ है कि वे एक सामान्य पूर्वज साझा कर सकते हैं। एल्गोरिदम मान लीजिए और संरेखित किए जाने वाले अनुक्रम हों, जहां और क्रमशः लंबाई हैं। प्रतिस्थापन मैट्रिक्स और अंतराल दंड योजना का निर्धारण करें। - उन तत्वों का समानता स्कोर जो दो अनुक्रमों का गठन करते हैं-एक अंतराल का दंड जिसकी लंबाई है एक स्कोरिंग मैट्रिक्स का निर्माण करें और इसकी पहली पंक्ति और पहले कॉलम को आरंभ करें। स्कोरिंग मैट्रिक्स का आकार है। मैट्रिक्स 0-आधारित अनुक्रमण का उपयोग करता है। नीचे दिए गए समीकरण का उपयोग करके स्कोरिंग मैट्रिक्स को भरें। संरेखण का स्कोर कहाँ है और, क्या स्कोर है यदि लंबाई के अंतराल के अंत में है, तो क्या स्कोर है यदि लंबाई के अंतराल के अंत में है, इसका मतलब है कि और तक कोई समानता नहीं है। ट्रेसबैक। स्कोरिंग मैट्रिक्स में उच्चतम स्कोर से शुरू करके और एक मैट्रिक्स सेल पर समाप्त होता है जिसमें 0 का स्कोर होता है, सर्वश्रेष्ठ स्थानीय संरेखण उत्पन्न करने के लिए प्रत्येक स्कोर के स्रोत के आधार पर पुनरावर्ती ट्रेसबैक। व्याख्या स्मिथ-वाटरमैन एल्गोरिथ्म मिलान/बेमेल (जिसे प्रतिस्थापन के रूप में भी जाना जाता है), सम्मिलन और विलोपन द्वारा दो अनुक्रमों को संरेखित करता है। सम्मिलन और विलोपन दोनों ऐसे ऑपरेशन हैं जो अंतराल पेश करते हैं, जिन्हें डैश द्वारा दर्शाया जाता है। स्मिथ-वाटरमैन एल्गोरिथम के कई चरण हैंः प्रतिस्थापन मैट्रिक्स और अंतराल दंड योजना का निर्धारण करें। एक प्रतिस्थापन मैट्रिक्स क्षार या अमीनो एसिड की प्रत्येक जोड़ी को मिलान या बेमेल के लिए एक अंक प्रदान करता है। आम तौर पर मैचों में सकारात्मक अंक मिलते हैं, जबकि बेमेल मुकाबलों में अपेक्षाकृत कम अंक मिलते हैं। एक अंतराल दंड कार्य अंतराल को खोलने या बढ़ाने के लिए अंक लागत निर्धारित करता है। यह सुझाव दिया जाता है कि उपयोगकर्ता लक्ष्यों के आधार पर उपयुक्त स्कोरिंग प्रणाली का चयन करें। इसके अलावा, प्रतिस्थापन मैट्रिक्स और अंतराल दंड के विभिन्न संयोजनों को आजमाना भी एक अच्छा अभ्यास है। स्कोरिंग मैट्रिक्स को प्रारंभ करें। स्कोरिंग मैट्रिक्स के आयाम प्रत्येक अनुक्रम की क्रमशः 1 + लंबाई हैं। पहली पंक्ति और पहले कॉलम के सभी तत्वों को 0 पर सेट किया गया है। अतिरिक्त पहली पंक्ति और पहला कॉलम किसी भी स्थिति में एक अनुक्रम को दूसरे से संरेखित करना संभव बनाता है, और उन्हें 0 पर सेट करने से अंतिम अंतराल दंड से मुक्त हो जाता है। स्कोरिंग। प्रतिस्थापन (विकर्ण अंक) या अंतराल जोड़ने (क्षैतिज और ऊर्ध्वाधर अंक) के परिणामों पर विचार करते हुए, मैट्रिक्स में प्रत्येक तत्व को बाएं से दाएं, ऊपर से नीचे तक स्कोर करें। यदि कोई भी अंक सकारात्मक नहीं है, तो इस तत्व को 0 मिलता है। अन्यथा उच्चतम अंक का उपयोग किया जाता है और उस अंक का स्रोत दर्ज किया जाता है। ट्रेसबैक। उच्चतम अंक के साथ तत्व से शुरू करते हुए, प्रत्येक अंक के स्रोत के आधार पर पुनरावर्ती रूप से ट्रेसबैक करें, जब तक कि 0 का सामना न हो जाए। इस प्रक्रिया में दिए गए अंक प्रणाली के आधार पर उच्चतम समानता अंक वाले खंड उत्पन्न होते हैं। दूसरा सर्वश्रेष्ठ स्थानीय संरेखण प्राप्त करने के लिए, सर्वश्रेष्ठ संरेखण के निशान के बाहर दूसरे उच्चतम अंक से शुरू होने वाली ट्रेसबैक प्रक्रिया को लागू करें। नीडलमैन-वुन्श एल्गोरिदम के साथ तुलना स्मिथ-वाटरमैन एल्गोरिदम दो अनुक्रमों में खंडों को पाता है जिनमें समानताएं हैं जबकि नीडलमैन-वुन्श एल्गोरिदम दो पूर्ण अनुक्रमों को संरेखित करता है। इसलिए, वे अलग-अलग उद्देश्यों की पूर्ति करते हैं। दोनों एल्गोरिदम एक प्रतिस्थापन मैट्रिक्स, एक अंतराल दंड कार्य, एक स्कोरिंग मैट्रिक्स और एक ट्रेसबैक प्रक्रिया की अवधारणाओं का उपयोग करते हैं। तीन मुख्य अंतर हैंः सबसे महत्वपूर्ण अंतरों में से एक यह है कि स्मिथ-वाटरमैन एल्गोरिदम की स्कोरिंग प्रणाली में कोई नकारात्मक अंक नहीं दिया जाता है, जो स्थानीय संरेखण को सक्षम बनाता है। जब किसी तत्व का अंक शून्य से कम होता है, तो इसका मतलब है कि इस स्थिति तक के अनुक्रमों में कोई समानता नहीं है; इस तत्व को तब शून्य पर सेट किया जाएगा ताकि पिछले संरेखण से प्रभाव को समाप्त किया जा सके। इस तरह, गणना बाद में किसी भी स्थिति में संरेखण ढूंढना जारी रख सकती है। स्मिथ-वाटरमैन एल्गोरिथम का प्रारंभिक स्कोरिंग मैट्रिक्स एक अनुक्रम के किसी भी खंड को दूसरे अनुक्रम में एक मनमाने स्थान पर संरेखित करने में सक्षम बनाता है। हालांकि, नीडलमैन-वुन्श एल्गोरिदम में, पूर्ण अनुक्रमों को संरेखित करने के लिए अंतिम अंतराल दंड पर भी विचार करने की आवश्यकता है। प्रतिस्थापन मैट्रिक्स प्रत्येक आधार प्रतिस्थापन या अमीनो एसिड प्रतिस्थापन को एक अंक दिया जाता है। सामान्य तौर पर, मैचों को सकारात्मक अंक दिए जाते हैं, और बेमेल को अपेक्षाकृत कम अंक दिए जाते हैं। डीएनए अनुक्रम को एक उदाहरण के रूप में लें। यदि मिलान + 1 प्राप्त करते हैं, तो बेमेल-1 प्राप्त करते हैं, तो प्रतिस्थापन मैट्रिक्स हैः इस प्रतिस्थापन मैट्रिक्स को इस प्रकार वर्णित किया जा सकता हैः विभिन्न आधार प्रतिस्थापन या अमीनो एसिड प्रतिस्थापन के अलग-अलग अंक हो सकते हैं। अमीनो एसिड का प्रतिस्थापन मैट्रिक्स आमतौर पर क्षार की तुलना में अधिक जटिल होता है। पी. ए. एम., बी. एल. ओ. एस. एम. देखें। गैप पेनल्टी गैप पेनल्टी प्रविष्टि या विलोपन के लिए अंक निर्धारित करती है। एक सरल अंतराल दंड रणनीति प्रत्येक अंतराल के लिए निश्चित अंक का उपयोग करना है। जीव विज्ञान में, हालांकि, व्यावहारिक कारणों से अंक को अलग तरीके से गिने जाने की आवश्यकता है। एक ओर, दो अनुक्रमों के बीच आंशिक समानता एक सामान्य घटना है; दूसरी ओर, एक एकल जीन उत्परिवर्तन घटना के परिणामस्वरूप एक लंबे अंतराल का सम्मिलन हो सकता है। इसलिए, एक लंबे अंतराल को बनाने वाले जुड़े अंतराल आमतौर पर कई बिखरे हुए, छोटे अंतराल की तुलना में अधिक अनुकूल होते हैं। इस अंतर को ध्यान में रखने के लिए, अंतराल खोलने और अंतराल विस्तार की अवधारणाओं को स्कोरिंग प्रणाली में जोड़ा गया है। गैप ओपनिंग स्कोर आमतौर पर गैप एक्सटेंशन स्कोर से अधिक होता है। उदाहरण के लिए, ई. एम. बी. ओ. एस. एस. वाटर में डिफ़ॉल्ट पैरामीटर हैंः गैप ओपनिंग = 10, गैप एक्सटेंशन = 0.5। यहाँ हम अंतराल दंड के लिए दो सामान्य रणनीतियों पर चर्चा करते हैं। अधिक रणनीतियों के लिए गैप पेनल्टी देखें। मान लीजिए कि लंबाई के अंतराल के लिए अंतराल दंड फलन हैः रैखिक एक रैखिक अंतराल दंड में अंतराल को खोलने और बढ़ाने के लिए समान अंक होते हैंः, जहां एकल अंतराल की लागत है। अंतराल दंड अंतराल की लंबाई के सीधे आनुपातिक होता है। जब रैखिक अंतराल दंड का उपयोग किया जाता है, तो स्मिथ-वाटरमैन एल्गोरिथ्म को सरल बनाया जा सकता हैः सरलीकृत एल्गोरिथ्म चरणों का उपयोग करता है। जब किसी तत्व को स्कोर किया जा रहा होता है, तो केवल उन तत्वों से अंतराल दंड पर विचार करने की आवश्यकता होती है जो सीधे इस तत्व से सटे होते हैं। एफ़ाइन गैप पेनल्टी गैप ओपनिंग और एक्सटेंशन को अलग से मानती हैः, जहाँ गैप ओपनिंग पेनल्टी है, और गैप एक्सटेंशन पेनल्टी है। उदाहरण के लिए, लंबाई 2 के अंतराल के लिए दंड है। मूल स्मिथ-वाटरमैन एल्गोरिदम पेपर में एक मनमाने अंतराल दंड का उपयोग किया गया था। यह कदमों का उपयोग करता है, इसलिए समय की काफी मांग है। गोटोह ने एफ़ाइन गैप पेनल्टी के लिए चरणों को अनुकूलित किया, लेकिन अनुकूलित एल्गोरिथ्म केवल एक इष्टतम संरेखण खोजने का प्रयास करता है, और इष्टतम संरेखण मिलने की गारंटी नहीं है। आल्ट्सचुल ने कम्प्यूटेशनल जटिलता को बनाए रखते हुए सभी इष्टतम संरेखण खोजने के लिए गोटोह के एल्गोरिथ्म को संशोधित किया। बाद में, मायर्स और मिलर ने बताया कि गोटोह और आल्ट्सचुल के एल्गोरिदम को 1975 में हिर्शबर्ग द्वारा प्रकाशित विधि के आधार पर और संशोधित किया जा सकता है, और इस विधि को लागू किया जा सकता है। मायर्स और मिलर का एल्गोरिथ्म स्थान का उपयोग करके दो अनुक्रमों को संरेखित कर सकता है, जिसमें छोटे अनुक्रम की लंबाई होती है। चौधरी, ले और रामचंद्रन ने बाद में दिखाया कि हिर्शबर्ग द्वारा उपयोग की जाने वाली रणनीति की तुलना में एक अलग पुनरावर्ती विभाजन और विजय रणनीति का उपयोग करके गोटोह के कैशे एल्गोरिदम को रैखिक स्थान में कुशलता से कैसे चलाया जाए। परिणामस्वरूप एल्गोरिथ्म अपने बेहतर कैश प्रदर्शन के कारण व्यवहार में मायर्स और मिलर के एल्गोरिथ्म की तुलना में तेजी से चलता है। अंतराल दंड का उदाहरण अनुक्रमों के संरेखण को एक उदाहरण के रूप में लें। जब रैखिक अंतराल दंड फलन का उपयोग किया जाता है, तो परिणाम होता है (एम्बॉस वाटर द्वारा किए गए संरेखण। प्रतिस्थापन मैट्रिक्स डी. एन. ए. फुल है (समानता स्कोरः + 5 अक्षरों के मिलान के लिए अन्यथा-4)। गैप ओपनिंग और एक्सटेंशन क्रमशः 0 और 1 हैं): जब एफ़ाइन गैप पेनल्टी का उपयोग किया जाता है, तो परिणाम यह होता है (गैप ओपनिंग और एक्सटेंशन क्रमशः 5 और 1 होते हैं): यह उदाहरण दर्शाता है कि एफ़ाइन गैप पेनल्टी बिखरे हुए छोटे अंतराल से बचने में मदद कर सकती है। स्कोरिंग मैट्रिक्स का कार्य दो अनुक्रमों में सभी घटकों के बीच एक-से-एक तुलना करना और इष्टतम संरेखण परिणामों को रिकॉर्ड करना है। स्कोरिंग प्रक्रिया गतिशील प्रोग्रामिंग की अवधारणा को दर्शाती है। अंतिम इष्टतम संरेखण बार-बार बढ़ते इष्टतम संरेखण का विस्तार करके पाया जाता है। दूसरे शब्दों में, वर्तमान इष्टतम संरेखण यह तय करके उत्पन्न किया जाता है कि कौन सा मार्ग (मिलान/बेमेल या अंतर डालने) पिछले इष्टतम संरेखण से उच्चतम अंक देता है। मैट्रिक्स का आकार एक अनुक्रम की लंबाई प्लस 1 बाय दूसरे अनुक्रम की लंबाई प्लस 1 है। अतिरिक्त पहली पंक्ति और पहला स्तंभ एक अनुक्रम को दूसरे अनुक्रम में किसी भी स्थिति के साथ संरेखित करने के उद्देश्य को पूरा करते हैं। पहली पंक्ति और पहले कॉलम दोनों को 0 पर सेट किया गया है ताकि अंतिम अंतराल को दंडित न किया जाए। प्रारंभिक स्कोरिंग मैट्रिक्स हैः उदाहरण के लिए डीएनए अनुक्रमों के संरेखण को लें और एक उदाहरण के रूप में। निम्नलिखित योजना का उपयोग करेंः प्रतिस्थापन मैट्रिक्सः अंतराल दंडः (का एक रैखिक अंतराल दंड) आरंभ करें और स्कोरिंग मैट्रिक्स को भरें, जो नीचे दिखाया गया है। यह आंकड़ा पहले तीन तत्वों की स्कोरिंग प्रक्रिया को दर्शाता है। पीला रंग उन आधारों को इंगित करता है जिन पर विचार किया जा रहा है। लाल रंग प्राप्त किए जा रहे कक्ष के लिए उच्चतम संभव अंक को इंगित करता है। तैयार स्कोरिंग मैट्रिक्स नीचे बाईं ओर दिखाया गया है। नीला रंग उच्चतम अंक दर्शाता है। एक तत्व एक से अधिक तत्वों से अंक प्राप्त कर सकता है, यदि इस तत्व का पता लगाया जाता है तो प्रत्येक एक अलग रास्ता बनाएगा। कई उच्चतम अंकों के मामले में, ट्रेसबैक प्रत्येक उच्चतम अंक से शुरू किया जाना चाहिए। ट्रेसबैक प्रक्रिया नीचे दाईं ओर दिखाई गई है। सबसे अच्छा स्थानीय संरेखण विपरीत दिशा में उत्पन्न होता है। संरेखण का परिणाम हैः स्मिथ-वाटरमैन एल्गोरिदम का कार्यान्वयन, SSEARCH, यूवीए फास्टा डाउनलोड से फास्टा अनुक्रम विश्लेषण पैकेज में उपलब्ध है। इस कार्यान्वयन में पावरपीसी जी4 और जी5 प्रोसेसर के लिए अल्टिवेक त्वरित कोड शामिल है जो वोजनियाक, 1997 दृष्टिकोण के संशोधन का उपयोग करके तुलना को गति देता है, और फरार द्वारा विकसित एक एस. एस. ई. 2 वेक्टराइजेशन जो इष्टतम प्रोटीन अनुक्रम डेटाबेस खोजों को काफी व्यावहारिक बनाता है। एक पुस्तकालय, एसएसडब्ल्यू, इष्टतम स्मिथ-वाटरमैन स्कोर के अलावा संरेखण जानकारी वापस करने के लिए फरार के कार्यान्वयन का विस्तार करता है। त्वरित संस्करण एफ. पी. जी. ए. क्रे ने एफ. पी. जी. ए. चिप्स पर आधारित एक पुनर्संयोजन योग्य कंप्यूटिंग प्लेटफॉर्म का उपयोग करके स्मिथ-वाटरमैन एल्गोरिदम के त्वरण का प्रदर्शन किया, जिसके परिणाम मानक माइक्रोप्रोसेसर-आधारित समाधानों पर 28 गुना गति तक दिखाई देते हैं। स्मिथ-वाटरमैन एल्गोरिथम का एक अन्य एफ. पी. जी. ए.-आधारित संस्करण एफ. पी. जी. ए. (वर्टेक्स-4) की गति को 2.2 गीगाहर्ट्ज़ ऑप्टेरॉन प्रोसेसर पर 100 गुना तक दिखाता है। टाइमलॉजिक डिसाइफर और कोडक्वेस्ट सिस्टम भी पीसीआईई एफ. पी. जी. ए. कार्ड का उपयोग करके स्मिथ-वाटरमैन और फ्रेम सर्च को तेज करते हैं। 2011 के मास्टर की थीसिस में एफ. पी. जी. ए. आधारित स्मिथ-वाटरमैन त्वरण का विश्लेषण शामिल है। ज़िलिंक्स एसडीएसेल के साथ संकलित 2016 के एक प्रकाशन ओपनसीएल कोड में जीनोम अनुक्रमण को गति देता है, सीपीयू/जीपीयू प्रदर्शन/डब्ल्यू को 12-21 एक्स द्वारा हरा देता है, एक बहुत ही कुशल कार्यान्वयन प्रस्तुत किया गया था। ज़िलिंक्स विरटेक्स-7 2000टी एफ. पी. जी. ए. से लैस एक पी. सी. आई. ई. एफ. पी. जी. ए. कार्ड का उपयोग करते हुए, प्रति वाट स्तर पर प्रदर्शन सी. पी. यू./जी. पी. यू. से 12-21 एक्स. से बेहतर था। जी. पी. यू. लॉरेंस लिवरमोर राष्ट्रीय प्रयोगशाला और संयुक्त राज्य अमेरिका (यू. एस.) ऊर्जा विभाग के संयुक्त जीनोम संस्थान ने ग्राफिक्स प्रसंस्करण इकाइयों (जी. पी. यू.) का उपयोग करके स्मिथ-वाटरमैन स्थानीय अनुक्रम संरेखण खोजों के एक त्वरित संस्करण को लागू किया, जिसमें प्रारंभिक परिणाम सॉफ्टवेयर कार्यान्वयन की तुलना में 2 गुना गति दिखाते हैं। इसी तरह की विधि पहले से ही 1997 से बायोफैसेट सॉफ्टवेयर में लागू की गई है, उसी गति-वृद्धि कारक के साथ। एनवीडिया के सीयूडीए सी प्लेटफॉर्म में एल्गोरिदम के कई जीपीयू कार्यान्वयन भी उपलब्ध हैं। फारार द्वारा सबसे प्रसिद्ध सीपीयू कार्यान्वयन (x86 वास्तुकला पर सिमडी निर्देशों का उपयोग करते हुए) की तुलना में, एकल एनवीडिया जीफोर्स 8800 जीटीएक्स कार्ड का उपयोग करके इस समाधान के प्रदर्शन परीक्षण छोटे अनुक्रमों के लिए प्रदर्शन में थोड़ी वृद्धि दिखाते हैं, लेकिन बड़े के लिए प्रदर्शन में थोड़ी कमी। हालांकि, दोहरे एनवीडिया जीफोर्स 8800 जीटीएक्स कार्ड पर चलने वाले समान परीक्षण सभी अनुक्रम आकारों के लिए फरार कार्यान्वयन की तुलना में लगभग दोगुने तेज हैं। एस. डब्ल्यू. का एक नया जी. पी. यू. सी. यू. डी. ए. कार्यान्वयन अब उपलब्ध है जो पिछले संस्करणों की तुलना में तेज है और पूछताछ की लंबाई पर सीमाओं को भी हटा देता है। CUDASW + + देखें। सी. यू. डी. ए. पर ग्यारह अलग-अलग एस. डब्ल्यू. कार्यान्वयनों की सूचना दी गई है, जिनमें से तीन 30X की गति की सूचना देते हैं। एस. आई. एम. डी. 2000 में, रॉग्नेस और सीबर्ग द्वारा एक प्रकाशन में एकल निर्देश, इंटेल पेंटियम एम. एम. एक्स. प्रोसेसर और इसी तरह की तकनीक में उपलब्ध एकाधिक डेटा (एस. आई. एम. डी.) तकनीक का उपयोग करते हुए स्मिथ-वाटरमैन एल्गोरिदम के तेजी से कार्यान्वयन का वर्णन किया गया था। वोजनियाक (1997) दृष्टिकोण के विपरीत, नया कार्यान्वयन प्रश्न अनुक्रम के समानांतर वैक्टर पर आधारित था, न कि विकर्ण वैक्टर पर। सेनसेल बायोइनफॉर्मेटिक्स कंपनी ने इस दृष्टिकोण को शामिल करते हुए एक पेटेंट के लिए आवेदन किया है। सेनसेल सॉफ्टवेयर को आगे विकसित कर रहा है और शैक्षणिक उपयोग के लिए निष्पादन योग्य मुफ्त प्रदान करता है। एल्गोरिथम (फरार, 2007) का एक एस. एस. ई. 2 वेक्टराइजेशन अब एस. एस. ई. 2 एक्सटेंशन के साथ इंटेल/ए. एम. डी. प्रोसेसर पर एक 8-16-गुना गति प्रदान करने के लिए उपलब्ध है। कोर माइक्रोआर्किटेक्चर का उपयोग करते हुए इंटेल प्रोसेसर पर चलने पर एस. एस. ई. 2 कार्यान्वयन में 20 गुना वृद्धि होती है। फरार का एस. एस. ई. 2 कार्यान्वयन फास्टा अनुक्रम तुलना पैकेज में एस. एस. ई. ए. आर. सी. एच. कार्यक्रम के रूप में उपलब्ध है। एस. एस. ई. ए. आर. सी. एच. को यूरोपीय जैव सूचना विज्ञान संस्थान के समानता खोज कार्यक्रमों में शामिल किया गया है। सार्वजनिक रूप से उपलब्ध एक श्वेत पत्र के अनुसार, डेनिश जैव सूचना विज्ञान कंपनी सी. एल. सी. बायो ने इंटेल 2.17 गीगाहर्ट्ज़ कोर 2 डुओ सी. पी. यू. पर एस. एस. ई. 2 के साथ मानक सॉफ्टवेयर कार्यान्वयन में लगभग 200 की गति हासिल की है। इंटेल और एडवांस्ड माइक्रो डिवाइसेस (ए. एम. डी.) आधारित लिनक्स सर्वरों पर स्मिथ-वाटरमैन एल्गोरिदम का त्वरित संस्करण, बायोसिलेशन द्वारा प्रस्तुत जेनकोर 6 पैकेज द्वारा समर्थित है। इस सॉफ्टवेयर पैकेज के प्रदर्शन मानक एक ही प्रोसेसर पर मानक सॉफ्टवेयर कार्यान्वयन के सापेक्ष 10 गुना गति त्वरण तक दिखाते हैं। वर्तमान में स्मिथ-वाटरमैन को गति देने वाले एस. एस. ई. और एफ. पी. जी. ए. दोनों समाधानों की पेशकश करने वाली जैव सूचना विज्ञान की एकमात्र कंपनी, सी. एल. सी. बायो ने सी. एल. सी. जैव सूचना विज्ञान क्यूब के साथ मानक सॉफ्टवेयर कार्यान्वयन में 110 से अधिक की गति हासिल की है। एसएसएसई3 के साथ सीपीयू पर एल्गोरिदम का सबसे तेज़ कार्यान्वयन स्वाइप सॉफ्टवेयर (रोगनेस, 2011) पाया जा सकता है, जो जीएनयू एफ़ेरो जनरल पब्लिक लाइसेंस के तहत उपलब्ध है। समानांतर में, यह सॉफ्टवेयर सोलह अलग-अलग डेटाबेस अनुक्रमों से अवशेषों की तुलना एक प्रश्न अवशेष से करता है। 375 अवशेष प्रश्न अनुक्रम का उपयोग करते हुए एक दोहरे इंटेल ज़ीऑन एक्स5650 छह-कोर प्रोसेसर प्रणाली पर 106 बिलियन सेल अपडेट प्रति सेकंड (जी. सी. यू. पी. एस.) की गति हासिल की गई, जो फरार के 'धारीदार' दृष्टिकोण पर आधारित सॉफ्टवेयर की तुलना में छह गुना अधिक तेज है। BLOSUM50 मैट्रिक्स का उपयोग करते समय यह BLAST से तेज होता है। सी और सी + + में डायगोनल्सडब्ल्यू नामक स्मिथ-वाटरमैन के कार्यान्वयन में सिमडी निर्देश सेट (x86 प्लेटफॉर्म के लिए SSE4.1 और पावरपीसी प्लेटफॉर्म के लिए अल्टीवेक) का उपयोग किया जाता है। यह एक ओपन-सोर्स एम. आई. टी. लाइसेंस के तहत जारी किया गया है। सेल ब्रॉडबैंड इंजन 2008 में, फरार ने सेल ब्रॉडबैंड इंजन के लिए धारीदार स्मिथ-वाटरमैन के एक बंदरगाह का वर्णन किया और एक आईबीएम क्यूएस20 ब्लेड और एक सोनी प्लेस्टेशन 3 पर क्रमशः 32 और 12 जीसीयूपीएस की गति की सूचना दी। सीमाएँ आनुवंशिक डेटा का तेजी से विस्तार वर्तमान डीएनए अनुक्रम संरेखण एल्गोरिदम की गति को चुनौती देता है। डी. एन. ए. वैरिएंट की खोज के लिए एक कुशल और सटीक विधि के लिए आवश्यक आवश्यकताएं वास्तविक समय में समानांतर प्रसंस्करण के लिए नवीन दृष्टिकोण की मांग करती हैं। वर्तमान विद्युत कार्यान्वयन के आशाजनक विकल्प के रूप में ऑप्टिकल कंप्यूटिंग दृष्टिकोण का सुझाव दिया गया है। ऑप्टकैम इस तरह के दृष्टिकोण का एक उदाहरण है। बायोइन्फॉर्मेटिक्स अनुक्रम संरेखण भी देखें अनुक्रम खनन नीडलमैन-वुन्श एल्गोरिथ्म लेवेंस्टीन दूरी ब्लास्ट फास्ट संदर्भ बाहरी लिंक जेएलाइनर-स्मिथ-वाटरमैन एल्गोरिथ्म B.A.B.A का एक खुला स्रोत जावा कार्यान्वयन। - एक एप्लेट (स्रोत के साथ) जो ई. बी. आई. यू. जी. ई. एन. ई. स्मिथ-वाटरमैन प्लगइन में एल्गोरिदम एफ. ए. एस. टी. ए./एस. एस. ई. ए. आर. सी. एच.-सेवा पृष्ठ को दृष्टिगत रूप से समझाता है-सी + + ओ. पी. ए. एल. में लिखे गए ग्राफिकल इंटरफेस के साथ एल्गोरिदम का एक ओपन सोर्स एस. एस. ई. ए. आर. सी. एच. संगत कार्यान्वयन-बड़े पैमाने पर इष्टतम अनुक्रम संरेखण विकर्ण के लिए एक एस. आई. एम. डी. सी/सी + + लाइब्रेरी-एम. आई. टी. लाइसेंस एस. एस. डब्ल्यू. के तहत एस. आई. एम. डी. निर्देश सेट (विशेष रूप से SSE4.1) के साथ एक ओपन-सोर्स सी/सी + + कार्यान्वयन-एक ओपन-सोर्स सी + + लाइब्रेरी जो एम. आई. टी. लाइसेंस मधुर अनुक्रम संरेखण के तहत स्मिथ-वाटरमैन एल्गोरिदम के एस. आई. एम. डी. कार्यान्वयन के लिए एक ए. पी. आई. प्रदान करती है-मधुर अनुक्रम के लिए एक