Tree alignment
கணக்கீட்டு பைலோஜெனெடிக்ஸில், மர சீரமைப்பு என்பது பல வரிசை சீரமைப்புகள் அல்லது டிஎன்ஏ, ஆர்என்ஏ அல்லது புரதத்தின் மூன்று அல்லது அதற்கு மேற்பட்ட வரிசைகளின் சீரமைப்புகளை உற்பத்தி செய்வதில் அக்கறை கொண்ட ஒரு கணக்கீட்டு சிக்கலாகும். தொடர்ச்சிகள் ஒரு பைலோஜெனெடிக் மரமாக அமைக்கப்பட்டுள்ளன, இனங்கள் அல்லது வகைப்பாற்றல்களுக்கு இடையிலான பரிணாம உறவுகளை மாதிரியாக்குகின்றன. வரிசைகளுக்கு இடையிலான எடிட் தூரங்கள் மரத்தின் ஒவ்வொரு உள் செங்குத்துகளுக்கும் கணக்கிடப்படுகின்றன, அதாவது மரத்திற்குள் உள்ள அனைத்து எடிட் தூரங்களின் கூட்டுத்தொகையும் குறைக்கப்படுகிறது. நிர்வகிக்கக்கூடிய மர அளவு மற்றும் கணக்கீட்டு முயற்சிக்கு இடையிலான பல்வேறு பரிமாற்றங்களுடன் பல வழிமுறைகளில் ஒன்றைப் பயன்படுத்தி மர சீரமைப்பை அடைய முடியும். வரையறை உள்ளீடுஃ வரிசைகளின் தொகுப்பு, ஒரு பைலோஜெனெடிக் மரம் இலை-பெயரிடப்பட்டது மற்றும் வரிசைகளுக்கு இடையிலான தூர செயல்பாட்டைத் திருத்துகிறது. வெளியீடுஃ குறைக்கப்பட்ட உள் செங்குத்துகளின் லேபிளிங், இதன் இறுதிப் புள்ளிகளுக்கு இடையிலான எடிட் தூரம் எங்கே. பணி NP-கடினமானது. பின்னணி வரிசை சீரமைப்பு உயிர் தகவலியலில், தகவல் செயலாக்கத்தின் அடிப்படை முறை வரிசை தரவை வேறுபடுத்துவதாகும். உயிரியல் வரிசைகளில் செயல்பாடு, கட்டமைப்பு மற்றும் பரிணாமத் தகவல்களைக் கண்டறிய உயிரியலாளர்கள் இதைப் பயன்படுத்துகின்றனர். பின்வரும் பகுப்பாய்வுகள் வரிசை கூட்டத்தை அடிப்படையாகக் கொண்டவைஃ பைலோஜெனெடிக் பகுப்பாய்வு, ஹாப்லோடைப் ஒப்பீடு மற்றும் ஆர்என்ஏ கட்டமைப்பின் கணிப்பு. எனவே, வரிசை சீரமைப்பின் செயல்திறன் இந்த சிக்கல்களைத் தீர்ப்பதற்கான செயல்திறனை நேரடியாக பாதிக்கும். பகுத்தறிவு மற்றும் திறமையான வரிசை சீரமைப்பை வடிவமைப்பதற்காக, அல்காரிதம் வழித்தோன்றல் உயிர் தகவலியல் துறையில் ஆராய்ச்சியின் ஒரு முக்கியமான கிளையாக மாறுகிறது. பொதுவாக, வரிசை சீரமைப்பு என்பது இரண்டு அல்லது அதற்கு மேற்பட்ட கொடுக்கப்பட்ட சரங்களிலிருந்து எழுத்துக்களைச் சேர்ப்பதன் மூலமோ, எழுத்துக்களை நீக்குவதன் மூலமோ அல்லது ஒவ்வொரு சரத்திற்கும் ஒரு இடத்தை சேர்ப்பதன் மூலமோ மிகப்பெரிய ஒற்றுமையுடன் ஒரு சரத்தை உருவாக்குவதாகும். பல வரிசை சீரமைப்பு சிக்கல் பொதுவாக ஜோடி வாரியாக வரிசை சீரமைப்பை அடிப்படையாகக் கொண்டது மற்றும் தற்போது, ஒரு ஜோடி வாரியாக வரிசை சீரமைப்பு சிக்கலுக்கு, உயிரியலாளர்கள் அதன் உகந்த தீர்வைப் பெற ஒரு மாறும் நிரலாக்க அணுகுமுறையைப் பயன்படுத்தலாம். இருப்பினும், பல வரிசை சீரமைப்பு சிக்கல் இன்னும் உயிர் தகவலியலில் மிகவும் சவாலான சிக்கல்களில் ஒன்றாகும். ஏனென்றால், பல வரிசை சீரமைப்புக்கான உகந்த தீர்வை கண்டுபிடிப்பது ஒரு NP-முழுமையான சிக்கலாக நிரூபிக்கப்பட்டுள்ளது மற்றும் தோராயமான உகந்த தீர்வை மட்டுமே பெற முடியும். தூர மேட்ரிக்ஸ் முறை தூர முறை ஒரு ஜோடி சரங்களில் இயக்கப்படும்போது ஒரு வரிசை u ஐ மற்ற வரிசை v க்கு மாற்றுவதற்குத் தேவையான எழுத்துக்கள் செருகுதல், நீக்குதல் மற்றும் மாற்றீடுகளின் குறைந்தபட்ச செயல்பாட்டு எண்ணிக்கையை அளவிடுகிறது. எடிட் தூரத்தின் கணக்கீடு டைனமிக் நிரலாக்கத்தை அடிப்படையாகக் கொண்டிருக்கலாம், மேலும் சமன்பாடு O (|u | × |v |) நேரத்தில் உள்ளது, அங்கு |u | மற்றும் |v | ஆகியவை u மற்றும் v இன் நீளங்கள் ஆகும். எடிட் தூரத்தைக் கணக்கிட தொடர்ச்சியான செயல்பாடுகள் பயன்படுத்தப்படுவதால், வெவ்வேறு செயல்பாடுகள் வெவ்வேறு முடிவுகளை ஏற்படுத்தக்கூடும். மர சீரமைப்பு சிக்கலுக்கு உகந்த எடிட் தூர செயல்பாட்டைக் கண்டறிவது அவசியம். மர சீரமைப்பு மர சீரமைப்பு சிக்கல் ஒரு NP-கடினமான சிக்கலை விளைவிக்கிறது, அங்கு மதிப்பெண் முறைகள் மற்றும் எழுத்துக்களின் அளவுகள் கட்டுப்படுத்தப்படுகின்றன. உகந்த தீர்வைக் கண்டறியப் பயன்படுத்தப்படும் ஒரு வழிமுறையாக இதைக் காணலாம். இருப்பினும், அதன் செயல்திறனுக்கும் எண் வரிசைகளுக்கும் இடையே ஒரு அதிவேக உறவு உள்ளது, அதாவது வரிசையின் நீளம் மிகப் பெரியதாக இருக்கும்போது, முடிவுகளைப் பெறுவதற்குத் தேவையான கணக்கீட்டு நேரம் மிகவும் நீளமானது. தோராயமான உகந்த தீர்வைப் பெற நட்சத்திர சீரமைப்பைப் பயன்படுத்துவது மர சீரமைப்பைப் பயன்படுத்துவதை விட வேகமானது. இருப்பினும், பல வரிசை ஒற்றுமையின் அளவு எதுவாக இருந்தாலும், நட்சத்திர சீரமைப்பின் நேர சிக்கலானது வரிசை எண்ணின் சதுரம் மற்றும் வரிசை சராசரி நீளத்தின் சதுரத்துடன் விகிதாசார உறவைக் கொண்டுள்ளது. வழக்கம் போல், எம். எஸ். ஏ. வில் உள்ள வரிசை மிகவும் நீளமானது, அது திறமையற்றது அல்லது ஏற்றுக்கொள்ள முடியாதது. எனவே, நேர சிக்கலை நேரியல் ரீதியாகக் குறைப்பதற்கான சவால் மர சீரமைப்பில் உள்ள முக்கிய சிக்கல்களில் ஒன்றாகும். ஒருங்கிணைந்த உகப்பாக்கம் மூலோபாயம் ஒருங்கிணைந்த உகப்பாக்கம் என்பது எம்எஸ்ஏ சிக்கல்களைத் தீர்ப்பதற்கான ஒரு நல்ல உத்தி. ஒருங்கிணைந்த உகப்பாக்கம் மூலோபாயத்தின் யோசனை இந்த சிக்கலை தீர்க்க பல வரிசை சீரமைப்பை ஜோடி வரிசை சீரமைப்பாக மாற்றுவதாகும். அதன் உருமாற்ற மூலோபாயத்தைப் பொறுத்து, ஒருங்கிணைந்த உகப்பாக்கம் மூலோபாயத்தை மரம் சீரமைப்பு வழிமுறை மற்றும் நட்சத்திர சீரமைப்பு வழிமுறை என பிரிக்கலாம். கொடுக்கப்பட்ட பல-வரிசை தொகுப்புக்கு = {,.,}, n இலை முனைகளைக் கொண்ட ஒரு பரிணாம மரத்தைக் கண்டுபிடித்து, இந்த பரிணாம மரத்திற்கும் தொகுப்புக்கும் இடையே ஒன்றுக்கு ஒன்று உறவை நிறுவவும். பரிணாம மரத்தின் உள் முனைகளுக்கு வரிசையை ஒதுக்குவதன் மூலம், ஒவ்வொரு விளிம்பின் மொத்த மதிப்பெண்ணையும் கணக்கிடுகிறோம், மேலும் அனைத்து விளிம்புகளின் மதிப்பெண்களின் கூட்டுத்தொகையும் பரிணாம மரத்தின் மதிப்பெண்ணாகும். மர சீரமைப்பின் நோக்கம் ஒரு ஒதுக்கப்பட்ட வரிசையைக் கண்டுபிடிப்பதாகும், இது அதிகபட்ச மதிப்பெண்ணைப் பெற முடியும், மேலும் பரிணாம மரம் மற்றும் அதன் முனைகளின் ஒதுக்கப்பட்ட வரிசையிலிருந்து இறுதி பொருந்தும் முடிவைப் பெறுகிறது. நட்சத்திர சீரமைப்பை மர சீரமைப்பின் ஒரு சிறப்பு நிகழ்வாகக் காணலாம். நாம் நட்சத்திர சீரமைப்பைப் பயன்படுத்தும்போது, பரிணாம மரத்திற்கு ஒரே ஒரு உள் முனை மற்றும் n இலை முனைகள் மட்டுமே உள்ளன. உள் முனைக்கு ஒதுக்கப்பட்ட வரிசை, மைய வரிசை என்று அழைக்கப்படுகிறது. முக்கிய சொல் மரக் கோட்பாடு மற்றும் அஹோ-கோரசிக் தேடல் வழிமுறை பல வரிசை சீரமைப்பை ஜோடி வரிசை சீரமைப்பாக மாற்ற ஒருங்கிணைந்த உகப்பாக்கம் மூலோபாயம் பயன்படுத்தப்படும்போது, முக்கிய சிக்கல் "பல வரிசை சீரமைப்பின் செயல்திறனை எவ்வாறு மேம்படுத்துவது" என்பதிலிருந்து "ஜோடி வாரியான வரிசை சீரமைப்பின் செயல்திறனை எவ்வாறு மேம்படுத்துவது" என்று மாற்றப்படுகிறது. முக்கிய மரக் கோட்பாடு மற்றும் அஹோ-கோரசிக் தேடல் வழிமுறை ஆகியவை ஜோடி வாரியான வரிசை சீரமைப்பு சிக்கலைத் தீர்ப்பதற்கான ஒரு திறமையான அணுகுமுறையாகும். முக்கிய சொல் மரக் கோட்பாடு மற்றும் அஹோ-கோராசிக் தேடல் வழிமுறையை இணைப்பதன் நோக்கம் இந்த வகையான சிக்கலைத் தீர்ப்பதாகும்ஃ கொடுக்கப்பட்ட நீண்ட சரம் மற்றும் குறுகிய சரங்களின் தொகுப்புக்கு = {,,.,} (z bul N, z> 1), அனைத்தின் இருப்பிடத்தையும் கண்டறியவும். செட் மூலம் உற்பத்தி செய்யப்படும் முக்கிய சொல் மரம் பயன்படுத்தப்படுகிறது, பின்னர் இந்த முக்கிய சொல் மரத்துடன் அஹோ-கோராசிக் தேடல் வழிமுறை மூலம் தேடப்படுகிறது. T இல் உள்ள அனைத்தின் இருப்பிடத்தையும் கண்டறிய இந்த முறையைப் பயன்படுத்துவதற்கான மொத்த நேர சிக்கலானது O (+ +) ஆகும், இங்கு = | | (நீளம்), = ‡ | | (அனைத்தின் நீளங்களின் கூட்டுத்தொகை) மற்றும் அனைத்து நிகழ்வுகளின் கூட்டுத்தொகையைக் குறிக்கிறது. முக்கிய சொல் மரம் கோட்பாடு தொகுப்பின் முக்கிய சொல் மரம் = {,,.,} (z bul N, z> 1) ஒரு வேரூன்றிய மரம், அதன் வேர் K ஆல் குறிக்கப்படுகிறது, மேலும் இந்த முக்கிய சொல் மரம் திருப்தி அளிக்கிறதுஃ (1): ஒவ்வொரு விளிம்பும் ஒரு எழுத்தை தெளிவாக வரையறுக்கிறது. (2) ஒரே முனையிலிருந்து பிரிக்கப்பட்ட எந்த இரண்டு விளிம்புகளும் வெவ்வேறு எழுத்துக்களுடன் ஒத்திருக்க வேண்டும். (3) ஒவ்வொரு வடிவமும் (i = 1,2,., z) ஒரு முனைக்கு ஒத்திருக்கிறது, மேலும் ரூட் K இலிருந்து முனைக்கு செல்லும் பாதை சரத்தை சரியாக உச்சரிக்க முடியும். இந்த கே மரத்தின் ஒவ்வொரு இலை முனையிலும், இது தொகுப்பின் குறிப்பிட்ட வடிவங்களில் ஒன்றுக்கு ஒத்திருக்கிறது. ரூட் நோடில் இருந்து நோடுடன் இணைக்கப்பட்டுள்ள ஸ்ட்ரிங்கை குறிக்க இது பயன்படுத்தப்படுகிறது. பின்னர் மிக நீளமான பின்னொட்டு நீளத்தைக் குறிக்கப் பயன்படுத்தப்படும் (மேலும், இந்த பின்னொட்டு தொகுப்பில் உள்ள வடிவங்களில் ஒன்றின் முன்னொட்டு). முக்கிய சொல் மரத்தில் உள்ள வேர் முனையிலிருந்து இந்த முன்னொட்டு தேடுகிறது, மேலும் தேடல் முடிந்ததும் குறிக்கப்படும் கடைசி முனை. எடுத்துக்காட்டாக, செட் = {உருளைக்கிழங்கு, பச்சை குத்துதல், தியேட்டர், பிற}, மற்றும் முக்கிய சொல் மரம் வலதுபுறத்தில் காட்டப்பட்டுள்ளது. அந்த எடுத்துக்காட்டில், என்றால் = பொட்டாட், பின்னர் = |tat | = 3, மற்றும் முனையின் தோல்வி இணைப்பு அந்த படத்தில் காட்டப்பட்டுள்ளது. தோல்வியுற்ற இணைப்பை நிறுவுவது அஹோ-கோராசிக் வழிமுறையின் நேர சிக்கலை மேம்படுத்துவதற்கான திறவுகோலாகும். அசல் பல்லுறுப்புக்கோவை நேரத்தை தேடுவதற்கான நேரியல் நேரமாகக் குறைக்க இதைப் பயன்படுத்தலாம். எனவே, முக்கிய சொல் மரக் கோட்பாட்டின் மையப்பகுதி ஒரு முக்கிய சொல் மரத்தின் அனைத்து தோல்வி இணைப்புகளையும் (அதாவது அனைத்தையும் கண்டுபிடிப்பது) நேரியல் நேரத்தில் கண்டுபிடிப்பதாகும். வேர் முனையிலிருந்து குறைவான தூரம் அல்லது சமமாக இருக்கும் அனைத்து முனைகளும் காணப்படலாம் என்று கருதப்படுகிறது. ரூட் நோடிலிருந்து + 1 தூரத்தில் இருக்கும் நோடை பின்னர் தேடலாம். அதன் தாய் முனை, மற்றும் முனையால் குறிக்கப்படும் எழுத்து மற்றும், ஆகும். (1): முனையின் அடுத்த எழுத்து இருந்தால், இந்த விளிம்பின் மற்ற முனையை, மற்றும் = என அமைக்கலாம். (2): அனைத்து எழுத்துக்களும் அதன் சைல்ட் நோடுகளுக்கு இடையிலான அனைத்து விளிம்புகளையும் தேடுவதன் மூலம் இல்லையென்றால், பிளஸ் என்ற பின்னொட்டு ஆகும். இந்த பின்னொட்டு ரூட் நோடில் தொடங்கும் ஸ்ட்ரிங்குடன் பொருந்துவதால் (முன்னொட்டு போன்றது), பின் கண்டுபிடிக்கப்படலாம் அல்லது இல்லை. இல்லையென்றால், இந்த செயல்முறையை ரூட் முனை காணப்படும் வரை தொடரலாம். அஹோ-கோராசிக் தேடல் வழிமுறை முக்கிய சொல் மரத்தில் அனைத்து தோல்வி இணைப்புகளையும் நிறுவிய பிறகு, அனைத்து இடங்களையும் (i = 1,2,., z) நேரியல் நேரத்தில் கண்டுபிடிக்க அஹோ-கோராசிக் தேடல் வழிமுறை பயன்படுத்தப்படுகிறது. இந்த கட்டத்தில், நேர சிக்கலானது O (m + k) ஆகும். பிற உத்திகள் எம்எஸ்ஏ, டிஎன்ஏ, ஆர்என்ஏ மற்றும் புரதங்களில், வரிசைகள் பொதுவாக உருவாக்கப்படுகின்றன, மேலும் அவை ஒரு பரிணாம உறவைக் கொண்டுள்ளன என்று கருதப்படுகிறது. ஆர்என்ஏ, டிஎன்ஏ ஆகியவற்றின் உருவாக்கப்பட்ட வரைபடங்கள் மற்றும் பரிணாமக் குடும்பங்களின் வரிசைகளை ஒப்பிடுவதன் மூலம், மக்கள் புரதங்களின் பாதுகாப்பை மதிப்பிடலாம் மற்றும் பரிணாமக் காட்சிகளுக்கு இடையிலான வேறுபாடுகளை ஒப்பிடுவதன் மூலம் செயல்பாட்டு மரபணு களங்களைக் கண்டறியலாம். பொதுவாக, பல வரிசை சீரமைப்பு சிக்கல்களைத் தீர்க்க ஹூரிஸ்டிக் வழிமுறைகள் மற்றும் மர சீரமைப்பு வரைபடங்களும் ஏற்றுக்கொள்ளப்படுகின்றன. ஹூரிஸ்டிக் அல்காரிதம் பொதுவாக, ஹூரிஸ்டிக் அல்காரிதம்கள் மறு செய்கை உத்தியை நம்பியுள்ளன, இது ஒரு ஒப்பீட்டு முறையின் அடிப்படையில், மறு செய்கை செயல்முறையால் பல வரிசை சீரமைப்பின் முடிவுகளை மேம்படுத்துகிறது. டேவி எம். பல வரிசை சீரமைப்பு சிக்கலைத் தீர்க்க துகள் திரள் உகப்பாக்கம் வழிமுறையைப் பயன்படுத்த முன்மொழிந்தார்; இக்கேடா தகாஹிரோ ஏ * தேடல் வழிமுறையை அடிப்படையாகக் கொண்ட ஒரு ஹூரிஸ்டிக் வழிமுறையை முன்மொழிந்தார்; ஈ. பிர்னி முதலில் மறைக்கப்பட்ட மார்கோவ் மாதிரியைப் பயன்படுத்தி பல வரிசை சீரமைப்பு சிக்கலைத் தீர்க்க முன்மொழிந்தார்; மேலும் பல உயிரியலாளர்கள் அதை தீர்க்க மரபணு வழிமுறையைப் பயன்படுத்துகின்றனர். இந்த வழிமுறைகள் அனைத்தும் பொதுவாக வலுவானவை மற்றும் வரிசைகளின் எண்ணிக்கைக்கு உணர்ச்சியற்றவை, ஆனால் அவை குறைபாடுகளையும் கொண்டுள்ளன. எடுத்துக்காட்டாக, துகள் திரள் உகப்பாக்கம் வழிமுறையின் முடிவுகள் நிலையற்றவை மற்றும் அதன் தகுதிகள் சீரற்ற எண்களின் தேர்வைப் பொறுத்தது, ஏ * தேடல் வழிமுறையின் இயக்க நேரம் மிக நீண்டது, மற்றும் மரபணு வழிமுறை உள்ளூர் சிறப்புக்குள் வருவது எளிது. மர சீரமைப்பு வரைபடம் தோராயமாக, மர சீரமைப்பு வரைபடம் மரங்களை ஒரு வரைபடத்தில் சீரமைப்பதையும், இறுதியாக புள்ளிவிவரங்களை உருவாக்க அவற்றை ஒருங்கிணைப்பதையும் நோக்கமாகக் கொண்டுள்ளது. உயிரியலில், மர சீரமைப்பு வரைபடங்கள் (டிஏஜி) மரங்களின் தொகுப்புகளிலிருந்து பரிணாம மோதல்கள் அல்லது ஒன்றுடன் ஒன்று வரும் வகைப்பாட்டை அகற்ற பயன்படுத்தப்படுகின்றன, பின்னர் நிச்சயமற்ற தன்மை மற்றும் மோதல்களை ஆராய்வதற்கு விசாரிக்கப்படலாம். சீரமைத்தல், ஒருங்கிணைத்தல் மற்றும் பகுப்பாய்வு முறைகளை ஒருங்கிணைப்பதன் மூலம், டிஏஜி முரண்பட்ட உறவுகள் மற்றும் பரந்த அளவிலான வரிசைகளிலிருந்து பெறப்பட்ட பகுதி ஒன்றுடன் ஒன்று வரிவிதிப்பு தொகுப்புகளைத் தீர்ப்பதை நோக்கமாகக் கொண்டுள்ளது. மேலும், மர சீரமைப்பு வரைபடம் சூப்பர் ட்ரீ மற்றும் கிராஃப்டிங் பயிற்சிகளுக்கான ஒரு அடிப்படை அணுகுமுறையாக செயல்படுகிறது, அவை பெர்ரியால் சூப்பர் ட்ரீகளை உருவாக்க வெற்றிகரமாக சோதிக்கப்பட்டுள்ளன. மரங்களிலிருந்து ஒரு வரைபடத்திற்கு மாற்றுவது அவற்றின் மூல மரங்களிலிருந்து ஒத்த முனைகள் மற்றும் விளிம்புகளைக் கொண்டிருப்பதால், மேலும் பகுப்பாய்விற்காக அசல் மூல மரங்களை பிரித்தெடுப்பதையும் டிஏஜி வழங்க முடியும். டிஏஜி என்பது சீரமைக்கும் மரங்களின் தொகுப்பாகும். இது முரண்பட்ட கருதுகோள்களை பரிணாம உறவை சேமித்து வைக்கலாம் மற்றும் பரிணாம கருதுகோள்களை உருவாக்க மூல மரங்களை ஒருங்கிணைக்கலாம். எனவே, மற்ற சீரமைப்பு சிக்கல்களைத் தீர்ப்பதற்கான ஒரு அடிப்படை முறையாகும். மேலும் காண்க பொதுமைப்படுத்தப்பட்ட மர சீரமைப்பு குறிப்புகள் கணக்கீட்டு பைலோஜெனெடிக்ஸ்