Tree alignment
कम्प्यूटेशनल फाइलोजेनेटिक्स में, वृक्ष संरेखण एक कम्प्यूटेशनल समस्या है जो कई अनुक्रम संरेखण, या डीएनए, आरएनए, या प्रोटीन के तीन या अधिक अनुक्रमों के संरेखण के उत्पादन से संबंधित है। अनुक्रमों को एक जातिजनित वृक्ष में व्यवस्थित किया जाता है, जो प्रजातियों या वर्ग के बीच विकासवादी संबंधों का प्रतिरूपण करता है। अनुक्रमों के बीच संपादन दूरी की गणना पेड़ के प्रत्येक आंतरिक शीर्ष के लिए की जाती है, जैसे कि पेड़ के भीतर सभी संपादन दूरी का योग न्यूनतम हो। वृक्ष संरेखण को प्रबंधनीय वृक्ष के आकार और कम्प्यूटेशनल प्रयास के बीच विभिन्न आदान-प्रदान के साथ कई एल्गोरिदम में से एक का उपयोग करके पूरा किया जा सकता है। परिभाषा इनपुटः अनुक्रमों का एक समूह, एक जातिजनित वृक्ष के पत्ते द्वारा लेबल किया गया और अनुक्रमों के बीच एक संपादन दूरी कार्य। आउटपुटः ऐसे आंतरिक शीर्षों की एक लेबलिंग जिसे न्यूनतम किया जाता है, जहां के अंतिम बिंदुओं के बीच संपादन दूरी होती है। यह कार्य एन. पी.-कठिन है। पृष्ठभूमि अनुक्रम संरेखण जैव सूचना विज्ञान में, सूचना प्रसंस्करण की मूल विधि अनुक्रम डेटा की तुलना करना है। जीवविज्ञानी इसका उपयोग जैविक अनुक्रमों में कार्य, संरचना और विकासवादी जानकारी की खोज के लिए करते हैं। निम्नलिखित विश्लेषण अनुक्रम संयोजन पर आधारित हैंः जातिजनित विश्लेषण, हैप्लोटाइप तुलना और आर. एन. ए. संरचना की भविष्यवाणी। इसलिए, अनुक्रम संरेखण की दक्षता इन समस्याओं को हल करने की प्रभावशीलता को सीधे प्रभावित करेगी। एक तर्कसंगत और कुशल अनुक्रम संरेखण तैयार करने के लिए, एल्गोरिथ्म व्युत्पत्ति जैव सूचना विज्ञान के क्षेत्र में अनुसंधान की एक महत्वपूर्ण शाखा बन जाती है। आम तौर पर, अनुक्रम संरेखण का अर्थ है अक्षरों को जोड़कर, अक्षरों को हटाकर या प्रत्येक स्ट्रिंग के लिए एक स्थान जोड़कर सबसे बड़ी समानता के साथ दो या दो से अधिक दिए गए स्ट्रिंग से एक स्ट्रिंग का निर्माण करना। एकाधिक अनुक्रम संरेखण समस्या आम तौर पर जोड़ीदार अनुक्रम संरेखण पर आधारित होती है और वर्तमान में, एक जोड़ीदार अनुक्रम संरेखण समस्या के लिए, जीवविज्ञानी इसका इष्टतम समाधान प्राप्त करने के लिए एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग कर सकते हैं। हालांकि, एकाधिक अनुक्रम संरेखण समस्या अभी भी जैव सूचना विज्ञान में अधिक चुनौतीपूर्ण समस्याओं में से एक है। ऐसा इसलिए है क्योंकि एकाधिक अनुक्रम संरेखण के लिए इष्टतम समाधान खोजना एक एनपी-पूर्ण समस्या के रूप में साबित हुआ है और केवल एक अनुमानित इष्टतम समाधान प्राप्त किया जा सकता है। दूरी मैट्रिक्स विधि दूरी विधि वर्ण सम्मिलन, विलोपन और प्रतिस्थापन की न्यूनतम संचालन संख्या को मापती है जो स्ट्रिंग की एक जोड़ी पर संचालित होने पर एक अनुक्रम यू को दूसरे अनुक्रम वी में बदलने के लिए आवश्यक होती है। संपादन दूरी की गणना गतिशील प्रोग्रामिंग पर आधारित हो सकती है, और समीकरण ओ (|u। × |v।) समय में है, जहाँ |u। और |v। यू और वी की लंबाई हैं। संपादन दूरी का कुशल अनुमान आवश्यक है क्योंकि दूरी विधि कम्प्यूटेशनल जीव विज्ञान में एक बुनियादी सिद्धांत है वंशानुगत गुणों के कार्यों के लिए "समरूपता" का उपयोग किया जा सकता है। संपादन दूरी की गणना करने के लिए उपयोग किए जाने वाले कार्यों की एक श्रृंखला के कारण, विभिन्न कार्यों के परिणामस्वरूप अलग-अलग परिणाम हो सकते हैं। वृक्ष संरेखण समस्या के लिए एक इष्टतम संपादन दूरी कार्य खोजना आवश्यक है। वृक्ष संरेखण की समस्या वृक्ष संरेखण के परिणामस्वरूप एक एन. पी.-कठिन समस्या होती है, जहाँ स्कोरिंग मोड और वर्णमाला के आकार प्रतिबंधित होते हैं। यह एक एल्गोरिथ्म के रूप में पाया जा सकता है, जिसका उपयोग अनुकूलित समाधान खोजने के लिए किया जाता है। हालाँकि, इसकी दक्षता और संख्या अनुक्रमों के बीच एक घातीय संबंध है, जिसका अर्थ है कि जब अनुक्रम की लंबाई बहुत बड़ी होती है, तो परिणाम प्राप्त करने के लिए आवश्यक गणना समय बहुत लंबा होता है। अनुमानित अनुकूलित समाधान प्राप्त करने के लिए तारा संरेखण का उपयोग करना वृक्ष संरेखण का उपयोग करने की तुलना में तेज़ है। हालांकि, बहु-अनुक्रम समानता की डिग्री जो भी हो, तारा संरेखण की समय जटिलता का अनुक्रम संख्या के वर्ग और अनुक्रम की औसत लंबाई के वर्ग के साथ आनुपातिक संबंध होता है। हमेशा की तरह, एम. एस. ए. में अनुक्रम इतना लंबा है कि यह अक्षम या अस्वीकार्य भी है। इसलिए, समय की जटिलता को रैखिक तक कम करने की चुनौती वृक्ष संरेखण में मुख्य मुद्दों में से एक है। एम. एस. ए. समस्याओं को हल करने के लिए संयोजन अनुकूलन रणनीति एक अच्छी रणनीति है। संयोजन अनुकूलन रणनीति का विचार इस समस्या को हल करने के लिए एकाधिक अनुक्रम संरेखण को जोड़ी अनुक्रम संरेखण में बदलना है। इसकी परिवर्तन रणनीति के आधार पर, संयोजन अनुकूलन रणनीति को ट्री संरेखण एल्गोरिदम और स्टार संरेखण एल्गोरिदम में विभाजित किया जा सकता है। किसी दिए गए बहु-अनुक्रम समुच्चय = {,.,} के लिए, एक विकासवादी वृक्ष खोजें जिसमें n पत्ती के नोड हों और इस विकासवादी वृक्ष और समुच्चय के बीच एक से एक संबंध स्थापित करें। विकासवादी वृक्ष के आंतरिक नोड्स को अनुक्रम निर्धारित करके, हम प्रत्येक किनारे के कुल स्कोर की गणना करते हैं, और सभी किनारों के स्कोर का योग विकासवादी वृक्ष का स्कोर होता है। वृक्ष संरेखण का उद्देश्य एक निर्दिष्ट अनुक्रम खोजना है, जो अधिकतम अंक प्राप्त कर सकता है, और विकासवादी वृक्ष और उसके नोड्स के निर्दिष्ट अनुक्रम से अंतिम मिलान परिणाम प्राप्त कर सकता है। तारों के संरेखण को वृक्ष संरेखण के एक विशेष मामले के रूप में देखा जा सकता है। जब हम तारा संरेखण का उपयोग करते हैं, तो विकासवादी वृक्ष में केवल एक आंतरिक नोड और एन लीफ नोड होते हैं। अनुक्रम, जो आंतरिक नोड को सौंपा जाता है, को कोर अनुक्रम कहा जाता है। मुख्य शब्द वृक्ष सिद्धांत और अहो-कोरासिक खोज एल्गोरिथ्म जब संयोजन अनुकूलन रणनीति का उपयोग एकाधिक अनुक्रम संरेखण को जोड़ी अनुक्रम संरेखण में बदलने के लिए किया जाता है, तो मुख्य समस्या को "कई अनुक्रम संरेखण की दक्षता में सुधार कैसे करें" से "जोड़ीदार अनुक्रम संरेखण की दक्षता में सुधार कैसे करें" में बदल दिया जाता है। कीवर्ड ट्री थ्योरी और अहो-कोरासिक खोज एल्गोरिदम जोड़ीदार अनुक्रम संरेखण समस्या को हल करने के लिए एक कुशल दृष्टिकोण है। मुख्य शब्द वृक्ष सिद्धांत और अहो-कोरासिक खोज एल्गोरिथ्म के संयोजन का उद्देश्य इस तरह की समस्या को हल करना हैः एक दी गई लंबी स्ट्रिंग और छोटी स्ट्रिंग के एक सेट के लिए = {,,.,} (z bul N, z> 1), सभी का स्थान ज्ञात करें। सेट द्वारा उत्पादित मुख्य शब्द ट्री का उपयोग किया जाता है, और फिर अहो-कोरासिक खोज एल्गोरिदम के माध्यम से इस मुख्य शब्द ट्री के साथ खोज की जाती है। टी में सभी के स्थान का पता लगाने के लिए इस विधि का उपयोग करने की कुल समय जटिलता ओ (+ +) है, जहाँ =।। (की लंबाई), =।। (सभी की लंबाई का योग) और इसका अर्थ है सभी के लिए घटना का योग। समूह का मुख्य शब्द वृक्ष = {,,.,} (z bul N, z> 1) एक जड़ वाला वृक्ष है, जिसका मूल K द्वारा दर्शाया गया है, और यह मुख्य शब्द वृक्ष संतुष्ट करता हैः (1): प्रत्येक किनारा स्पष्ट रूप से एक अक्षर का सीमांकन करता है। (2): एक ही नोड से अलग किए गए किसी भी दो किनारों को अलग-अलग अक्षरों के अनुरूप होना चाहिए। (3) प्रत्येक पैटर्न (i = 1,2,., z) एक नोड से मेल खाता है, और मूल K से नोड तक का मार्ग स्ट्रिंग की वर्तनी को बिल्कुल सही तरीके से लिख सकता है। इस के ट्री के प्रत्येक पत्ती नोड के लिए, यह सेट के कुछ पैटर्न में से एक से मेल खाता है। इसका उपयोग स्ट्रिंग का प्रतिनिधित्व करने के लिए किया जाता है जो रूट नोड से नोड से जुड़ा होता है। फिर सबसे लंबे प्रत्यय की लंबाई का प्रतिनिधित्व करने के लिए उपयोग किया जाएगा (साथ ही, यह प्रत्यय सेट में पैटर्न में से एक का उपसर्ग है)। इस उपसर्ग को खोजशब्द वृक्ष में मूल नोड से खोज रहे हैं, और अंतिम नोड द्वारा दर्शाया गया है जब खोज समाप्त हो जाती है। उदाहरण के लिए, सेट = {आलू, टैटू, थिएटर, अन्य}, और मुख्य शब्द ट्री दाईं ओर दिखाया गया है। उस उदाहरण में, यदि = पोटट, तो = |tat। = 3, और नोड की विफलता कड़ी उस आकृति में दिखाई गई है। अहो-कोरासिक एल्गोरिदम की समय जटिलता में सुधार के लिए एक विफलता कड़ी स्थापित करना महत्वपूर्ण है। इसका उपयोग मूल बहुपद समय को खोज के लिए रैखिक समय तक कम करने के लिए किया जा सकता है। इसलिए, मुख्य शब्द वृक्ष सिद्धांत का मूल रैखिक समय में एक मुख्य शब्द वृक्ष के सभी विफलता लिंक (जिसका अर्थ सभी एस को खोजना भी है) का पता लगाना है। यह माना जाता है कि सभी नोड्स, जिनकी रूट नोड से दूरी कम या बराबर है, पाए जा सकते हैं। उस नोड का, जिसकी रूट नोड से दूरी + 1 है, तब खोजा जा सकता है। इसका मूल नोड है, और नोड और द्वारा दर्शाया गया अक्षर है। (1): यदि नोड का अगला अक्षर है, तो इस किनारे के दूसरे नोड को, और = के रूप में सेट किया जा सकता है। (2): यदि सभी अक्षर और उनके चाइल्ड नोड्स के बीच के सभी किनारों को खोजना नहीं है, तो यह प्लस का प्रत्यय है। क्योंकि यह प्रत्यय मूल नोड (उपसर्ग के समान) से शुरू होने वाले स्ट्रिंग से मेल खाता है, इसलिए बाद का पता लगाया जा सकता है या नहीं। यदि नहीं, तो इस प्रक्रिया को तब तक जारी रखा जा सकता है जब तक कि रूट नोड नहीं मिल जाता। अहो-कोरासिक खोज एल्गोरिथ्म मुख्यशब्द वृक्ष में सभी विफलता लिंक स्थापित करने के बाद, अहो-कोरासिक खोज एल्गोरिथ्म का उपयोग रैखिक समय में सभी (i = 1,2,., z) के स्थानों को खोजने के लिए किया जाता है। इस चरण में, समय जटिलता ओ (एम + के) है। अन्य रणनीतियाँ एम. एस. ए., डी. एन. ए., आर. एन. ए. और प्रोटीन में, अनुक्रम आमतौर पर उत्पन्न होते हैं और उन्हें एक विकासवादी संबंध माना जाता है। आर. एन. ए., डी. एन. ए. के उत्पन्न मानचित्रों और विकासवादी परिवारों के अनुक्रमों की तुलना करके, लोग प्रोटीन के संरक्षण का आकलन कर सकते हैं और विकासवादी अनुक्रमों के बीच अंतर की तुलना करके कार्यात्मक जीन डोमेन का पता लगा सकते हैं। आम तौर पर, कई अनुक्रम संरेखण समस्याओं को हल करने के लिए ह्यूरिस्टिक एल्गोरिदम और ट्री संरेखण ग्राफ भी अपनाए जाते हैं। हेयुरिस्टिक एल्गोरिदम आम तौर पर, हेयुरिस्टिक एल्गोरिदम पुनरावृत्ति रणनीति पर निर्भर करते हैं, जो कि एक तुलना विधि पर आधारित है, जो पुनरावृत्ति प्रक्रिया द्वारा कई अनुक्रम संरेखण के परिणामों को अनुकूलित करता है। डेवी एम. ने एकाधिक अनुक्रम संरेखण समस्या को हल करने के लिए कण झुंड अनुकूलन एल्गोरिथ्म का उपयोग करने का प्रस्ताव रखा; इकेडा ताकाहिरो ने एक ह्यूरिस्टिक एल्गोरिथ्म का प्रस्ताव रखा जो ए * खोज एल्गोरिथ्म पर आधारित है; ई. बर्नी ने पहली बार एकाधिक अनुक्रम संरेखण समस्या को हल करने के लिए छिपे हुए मार्कोव मॉडल का उपयोग करने का प्रस्ताव रखा; और कई अन्य जीवविज्ञानी इसे हल करने के लिए आनुवंशिक एल्गोरिथ्म का उपयोग करते हैं। ये सभी एल्गोरिदम आम तौर पर अनुक्रमों की संख्या के प्रति मजबूत और असंवेदनशील होते हैं, लेकिन उनमें कमियां भी होती हैं। उदाहरण के लिए, कण झुंड अनुकूलन एल्गोरिदम के परिणाम अस्थिर हैं और इसके गुण यादृच्छिक संख्याओं के चयन पर निर्भर करते हैं, ए * खोज एल्गोरिदम का रनटाइम बहुत लंबा है, और आनुवंशिक एल्गोरिदम को स्थानीय उत्कृष्ट में गिरना आसान है। वृक्ष संरेखण ग्राफ मोटे तौर पर, वृक्ष संरेखण ग्राफ का उद्देश्य वृक्षों को एक ग्राफ में संरेखित करना और अंत में सांख्यिकी विकसित करने के लिए उन्हें संश्लेषित करना है। जीव विज्ञान में, वृक्ष संरेखण ग्राफ (टी. ए. जी.) का उपयोग पेड़ों के समूह से विकासवादी संघर्षों या अतिव्यापी टैक्स को हटाने के लिए किया जाता है और फिर अनिश्चितता और संघर्ष का पता लगाने के लिए उनसे पूछताछ की जा सकती है। संरेखण, संश्लेषण और विश्लेषण के तरीकों को एकीकृत करके, टीएजी का उद्देश्य परस्पर विरोधी संबंधों और अनुक्रमों की एक विस्तृत श्रृंखला से प्राप्त आंशिक अतिव्यापी वर्गीकरण सेटों को हल करना है। इसके अलावा, वृक्ष संरेखण ग्राफ सुपरट्री और ग्राफ्टिंग अभ्यासों के लिए एक मौलिक दृष्टिकोण के रूप में कार्य करता है, जिनका बेरी द्वारा सुपरट्री के निर्माण के लिए सफलतापूर्वक परीक्षण किया गया है। चूँकि पेड़ों से ग्राफ में परिवर्तन में उनके स्रोत पेड़ों से समान नोड और किनारे होते हैं, टीएजी आगे के विश्लेषण के लिए मूल स्रोत पेड़ों का निष्कर्षण भी प्रदान कर सकते हैं। टीएजी संरेखित पेड़ों के एक समूह का एक संयोजन है। यह परस्पर विरोधी परिकल्पनाओं के विकासवादी संबंधों को संग्रहीत कर सकता है और विकासवादी परिकल्पनाओं को विकसित करने के लिए स्रोत वृक्षों को संश्लेषित कर सकता है। इसलिए, यह अन्य संरेखण समस्याओं को हल करने का एक बुनियादी तरीका है। सामान्यीकृत वृक्ष संरेखण संदर्भ कम्प्यूटेशनल फाइलोजेनेटिक्स भी देखें।