Tree alignment
કોમ્પ્યુટેશનલ ફિલોજેનેટિક્સમાં, વૃક્ષ સંરેખણ એ એક કોમ્પ્યુટેશનલ સમસ્યા છે જે બહુવિધ અનુક્રમ સંરેખણ, અથવા ડીએનએ, આરએનએ અથવા પ્રોટીનના ત્રણ અથવા વધુ ક્રમની સંરેખણના ઉત્પાદન સાથે સંબંધિત છે. શ્રેણીઓને જાતિજન્ય વૃક્ષમાં ગોઠવવામાં આવે છે, જે પ્રજાતિઓ અથવા વર્ગ વચ્ચેના ઉત્ક્રાંતિ સંબંધોનું મોડેલિંગ કરે છે. ક્રમ વચ્ચેના સંપાદન અંતરની ગણતરી વૃક્ષના દરેક આંતરિક શિરોબિંદુઓ માટે કરવામાં આવે છે, જેથી વૃક્ષની અંદરના તમામ સંપાદન અંતરોનો સરવાળો ઓછો થાય. વૃક્ષની ગોઠવણી વ્યવસ્થાપિત વૃક્ષના કદ અને કોમ્પ્યુટેશનલ પ્રયત્નો વચ્ચેના વિવિધ વિનિમય સાથે અનેક અલ્ગોરિધમ્સમાંથી એકનો ઉપયોગ કરીને પૂર્ણ કરી શકાય છે. વ્યાખ્યા ઇનપુટઃ અનુક્રમોનો સમૂહ, દ્વારા લેબલ થયેલ ફિલોજેનેટિક વૃક્ષ પર્ણ અને અનુક્રમ વચ્ચે સંપાદન અંતર કાર્ય. આઉટપુટઃ આવા આંતરિક શિરોબિંદુઓનું લેબલિંગ કે જે ન્યૂનતમ છે, જ્યાં અંતિમ બિંદુઓ વચ્ચેનું સંપાદન અંતર છે. આ કાર્ય એન. પી.-હાર્ડ છે. પૃષ્ઠભૂમિ અનુક્રમ સંરેખણ બાયોઇન્ફોર્મેટિક્સમાં, માહિતી પ્રક્રિયાની મૂળભૂત પદ્ધતિ અનુક્રમ ડેટાની તુલના કરવાની છે. જીવવિજ્ઞાનીઓ તેનો ઉપયોગ જૈવિક અનુક્રમમાં કાર્ય, માળખું અને ઉત્ક્રાંતિ માહિતી શોધવા માટે કરે છે. નીચેના વિશ્લેષણ અનુક્રમ સમૂહ પર આધારિત છેઃ જાતિવૃત્તીય વિશ્લેષણ, હેપ્લોટાઇપ સરખામણી અને આર. એન. એ. માળખાની આગાહી. તેથી, અનુક્રમ સંરેખણની કાર્યક્ષમતા આ સમસ્યાઓના ઉકેલની અસરકારકતાને સીધી અસર કરશે. તર્કસંગત અને કાર્યક્ષમ અનુક્રમ સંરેખણની રચના કરવા માટે, અલ્ગોરિધમ વ્યુત્પત્તિ બાયોઇન્ફોર્મેટિક્સના ક્ષેત્રમાં સંશોધનની એક મહત્વપૂર્ણ શાખા બની જાય છે. સામાન્ય રીતે, અનુક્રમ સંરેખણનો અર્થ એ છે કે અક્ષરો ઉમેરીને, અક્ષરો કાઢીને અથવા દરેક શબ્દમાળા માટે જગ્યા ઉમેરીને સૌથી વધુ સમાનતા સાથે બે અથવા વધુ તારમાંથી શબ્દમાળા બનાવવી. બહુવિધ અનુક્રમ સંરેખણ સમસ્યા સામાન્ય રીતે જોડી મુજબની અનુક્રમ સંરેખણ પર આધારિત હોય છે અને હાલમાં, જોડી મુજબની અનુક્રમ સંરેખણ સમસ્યા માટે, જીવવિજ્ઞાનીઓ તેનો શ્રેષ્ઠ ઉકેલ મેળવવા માટે ગતિશીલ પ્રોગ્રામિંગ અભિગમનો ઉપયોગ કરી શકે છે. જો કે, બહુવિધ અનુક્રમ સંરેખણ સમસ્યા હજુ પણ બાયોઇન્ફોર્મેટિક્સમાં વધુ પડકારજનક સમસ્યાઓમાંની એક છે. આનું કારણ એ છે કે બહુવિધ અનુક્રમ સંરેખણ માટે શ્રેષ્ઠ ઉકેલ શોધવો એ એન. પી.-પૂર્ણ સમસ્યા તરીકે સાબિત થયું છે અને માત્ર અંદાજિત શ્રેષ્ઠ ઉકેલ મેળવી શકાય છે. અંતર મેટ્રિક્સ પદ્ધતિ અંતર પદ્ધતિ અક્ષરો દાખલ કરવા, કાઢી નાખવા અને અવેજની લઘુતમ કામગીરીની સંખ્યાને માપે છે જે શબ્દમાળાઓની જોડી પર સંચાલિત થાય ત્યારે એક ક્રમ u ને બીજા ક્રમ v માં રૂપાંતરિત કરવા માટે જરૂરી હોય છે. સંપાદન અંતરની ગણતરી ગતિશીલ પ્રોગ્રામિંગ પર આધારિત હોઈ શકે છે, અને સમીકરણ O (|u | × |v |) સમયમાં છે, જ્યાં |u | અને |v | એ u અને v ની લંબાઈ છે. સંપાદન અંતરનો કાર્યક્ષમ અંદાજ આવશ્યક છે કારણ કે ગણતરીત્મક જીવવિજ્ઞાનમાં અંતર પદ્ધતિ એ મૂળભૂત સિદ્ધાંત છે વારસાગત ગુણધર્મોના કાર્યો માટે "સમપ્રમાણતા" નો ઉપયોગ કરી શકાય છે. સંપાદન અંતરની ગણતરી કરવા માટે ઉપયોગમાં લેવાતા કાર્યોની શ્રેણીને કારણે, વિવિધ કાર્યો વિવિધ પરિણામોમાં પરિણમી શકે છે. વૃક્ષ સંરેખણ સમસ્યા માટે શ્રેષ્ઠ સંપાદન અંતર કાર્ય શોધવું જરૂરી છે. વૃક્ષ સંરેખણની સમસ્યા વૃક્ષ સંરેખણ એન. પી.-હાર્ડ સમસ્યામાં પરિણમે છે, જ્યાં સ્કોરિંગ સ્થિતિઓ અને મૂળાક્ષરોનું કદ પ્રતિબંધિત છે. તે એક અલ્ગોરિધમ તરીકે મળી શકે છે, જેનો ઉપયોગ શ્રેષ્ઠ ઉકેલ શોધવા માટે થાય છે. જો કે, તેની કાર્યક્ષમતા અને સંખ્યા ક્રમ વચ્ચે ઘાતાંકીય સંબંધ છે, જેનો અર્થ છે કે જ્યારે ક્રમની લંબાઈ ખૂબ મોટી હોય છે, ત્યારે પરિણામો મેળવવા માટે જરૂરી ગણતરીનો સમય ઘણો લાંબો હોય છે. અંદાજિત ઓપ્ટિમાઇઝ્ડ સોલ્યુશન મેળવવા માટે સ્ટાર સંરેખણનો ઉપયોગ કરવો એ વૃક્ષ સંરેખણનો ઉપયોગ કરતાં વધુ ઝડપી છે. જો કે, બહુવિધ-અનુક્રમ સમાનતાની માત્રા ગમે તે હોય, તારાની ગોઠવણીની સમય જટિલતા ક્રમ સંખ્યાના વર્ગ અને ક્રમની સરેરાશ લંબાઈના વર્ગ સાથે પ્રમાણસર સંબંધ ધરાવે છે. હંમેશની જેમ, એમ. એસ. એ. માં ક્રમ એટલો લાંબો છે કે તે બિનકાર્યક્ષમ અથવા અસ્વીકાર્ય પણ છે. તેથી, સમયની જટિલતાને રેખીયમાં ઘટાડવાનો પડકાર એ વૃક્ષ સંરેખણમાં મુખ્ય મુદ્દાઓમાંથી એક છે. સંયુક્ત ઓપ્ટિમાઇઝેશન વ્યૂહરચના સંયુક્ત ઓપ્ટિમાઇઝેશન એ એમ. એસ. એ. સમસ્યાઓ ઉકેલવા માટે એક સારી વ્યૂહરચના છે. સંયુક્ત ઓપ્ટિમાઇઝેશન વ્યૂહરચનાનો વિચાર આ સમસ્યાનું સમાધાન કરવા માટે બહુવિધ અનુક્રમ સંરેખણને જોડી અનુક્રમ સંરેખણમાં રૂપાંતરિત કરવાનો છે. તેની પરિવર્તન વ્યૂહરચનાના આધારે, સંયુક્ત ઓપ્ટિમાઇઝેશન વ્યૂહરચનાને વૃક્ષ સંરેખણ અલ્ગોરિધમ અને સ્ટાર સંરેખણ અલ્ગોરિધમમાં વિભાજિત કરી શકાય છે. આપેલ બહુ-અનુક્રમ સમૂહ = {,.,} માટે, એક ઉત્ક્રાંતિ વૃક્ષ શોધો જેમાં n પર્ણ ગાંઠો હોય અને આ ઉત્ક્રાંતિ વૃક્ષ અને સમૂહ વચ્ચે એકથી એક સંબંધ સ્થાપિત કરે. ઉત્ક્રાંતિ વૃક્ષના આંતરિક ગાંઠોને ક્રમ સોંપીને, આપણે દરેક ધારના કુલ ગુણાંકની ગણતરી કરીએ છીએ, અને તમામ ધારના ગુણાંકનો સરવાળો ઉત્ક્રાંતિ વૃક્ષનો ગુણાંક છે. વૃક્ષ સંરેખણનો ઉદ્દેશ એક નિર્ધારિત ક્રમ શોધવાનો છે, જે મહત્તમ સ્કોર મેળવી શકે છે, અને ઉત્ક્રાંતિ વૃક્ષ અને તેના ગાંઠોના નિયુક્ત ક્રમમાંથી અંતિમ મેળ ખાતું પરિણામ મેળવી શકે છે. તારાની ગોઠવણીને વૃક્ષની ગોઠવણીના વિશેષ કેસ તરીકે જોઈ શકાય છે. જ્યારે આપણે સ્ટાર સંરેખણનો ઉપયોગ કરીએ છીએ, ત્યારે ઉત્ક્રાંતિ વૃક્ષમાં માત્ર એક આંતરિક નોડ અને એન પર્ણ ગાંઠો હોય છે. આંતરિક નોડને સોંપવામાં આવેલ ક્રમને મુખ્ય ક્રમ કહેવામાં આવે છે. મુખ્ય શબ્દ વૃક્ષ સિદ્ધાંત અને અહો-કોરાસિક શોધ અલ્ગોરિધમ જ્યારે સંયુક્ત ઓપ્ટિમાઇઝેશન વ્યૂહરચનાનો ઉપયોગ બહુવિધ અનુક્રમ સંરેખણને જોડી અનુક્રમ સંરેખણમાં રૂપાંતરિત કરવા માટે કરવામાં આવે છે, ત્યારે મુખ્ય સમસ્યાને "બહુવિધ અનુક્રમ સંરેખણની કાર્યક્ષમતામાં સુધારો કેવી રીતે કરવો" થી "જોડી મુજબ અનુક્રમ સંરેખણની કાર્યક્ષમતામાં સુધારો કેવી રીતે કરવો" માં બદલવામાં આવે છે. કીવર્ડ ટ્રી થિયરી અને અહો-કોરાસિક સર્ચ અલ્ગોરિધમ એ જોડી મુજબ ક્રમ સંરેખણ સમસ્યાને ઉકેલવા માટે એક કાર્યક્ષમ અભિગમ છે. કીવર્ડ ટ્રી થિયરી અને અહો-કોરાસિક સર્ચ અલ્ગોરિધમનો સંયોજનનો ઉદ્દેશ આ પ્રકારની સમસ્યાનું સમાધાન કરવાનો છેઃ આપેલ લાંબી સ્ટ્રિંગ અને ટૂંકી સ્ટ્રિંગ્સના સમૂહ માટે = {,,.,} (z bul N, z> 1), બધામાં સ્થાન શોધો. સમૂહ દ્વારા ઉત્પન્ન થયેલ મુખ્ય શબ્દ વૃક્ષનો ઉપયોગ કરવામાં આવે છે, અને પછી અહો-કોરાસિક શોધ અલ્ગોરિધમ દ્વારા આ મુખ્ય શબ્દ વૃક્ષ સાથે શોધ કરવામાં આવે છે. T માં બધાનું સ્થાન શોધવા માટે આ પદ્ધતિનો ઉપયોગ કરવાની કુલ સમય જટિલતા O (+ +) છે, જ્યાં = | | (લંબાઈ), = ‡ | | (બધી લંબાઈનો સરવાળો) અને તેનો અર્થ થાય છે અંદરની તમામ ઘટનાઓનો સરવાળો. સમૂહનું મુખ્ય શબ્દ વૃક્ષ = {,,.,} (z bul N, z> 1) એક મૂળ વૃક્ષ છે, જેનું મૂળ K દ્વારા સૂચવવામાં આવે છે, અને આ મુખ્ય શબ્દ વૃક્ષ સંતોષે છેઃ (1): દરેક ધાર સ્પષ્ટપણે એક અક્ષરનું સીમાંકન કરે છે. (2): એક જ નોડથી અલગ થયેલ કોઈપણ બે ધાર અલગ-અલગ અક્ષરોને અનુરૂપ હોય છે. (3) દરેક પેટર્ન (i = 1,2,., z) નોડને અનુરૂપ છે, અને મૂળ K થી નોડ સુધીનો માર્ગ સ્ટ્રિંગની બરાબર યોગ્ય જોડણી કરી શકે છે. આ K વૃક્ષના દરેક પર્ણ નોડ માટે, તે સમૂહની ચોક્કસ પેટર્નમાંથી એકને અનુરૂપ છે. તેનો ઉપયોગ સ્ટ્રિંગનું પ્રતિનિધિત્વ કરવા માટે થાય છે જે રુટ નોડથી નોડ સાથે જોડાયેલ છે. પછી તેનો ઉપયોગ સૌથી લાંબા પ્રત્યયની લંબાઈને રજૂ કરવા માટે કરવામાં આવશે (ઉપરાંત, આ પ્રત્યય સમૂહમાં એક પેટર્નનો ઉપસર્ગ છે). કીવર્ડ ટ્રીમાં રુટ નોડમાંથી આ ઉપસર્ગને શોધવું, અને જ્યારે શોધ સમાપ્ત થાય ત્યારે સૂચવવામાં આવેલ છેલ્લો નોડ. ઉદાહરણ તરીકે, સમૂહ = {બટાટા, ટેટૂ, થિયેટર, અન્ય}, અને મુખ્ય શબ્દ વૃક્ષ જમણી બાજુએ દર્શાવવામાં આવ્યો છે. તે ઉદાહરણમાં, જો = પોટટ, તો = |tat | = 3, અને નોડની નિષ્ફળતા કડી તે આકૃતિમાં દર્શાવવામાં આવી છે. નિષ્ફળતા કડી સ્થાપિત કરવી એ અહો-કોરાસિક અલ્ગોરિધમનો સમય જટિલતા સુધારવા માટેની ચાવી છે. તેનો ઉપયોગ મૂળ બહુપદી સમયને શોધવા માટેના રેખીય સમય સુધી ઘટાડવા માટે થઈ શકે છે. તેથી, મુખ્ય શબ્દ વૃક્ષ સિદ્ધાંતનો મુખ્ય ભાગ રેખીય સમયમાં મુખ્ય શબ્દ વૃક્ષની તમામ નિષ્ફળતા કડીઓ (જેનો અર્થ એ પણ છે કે તમામ s શોધવી) શોધવાનો છે. એવું માનવામાં આવે છે કે દરેક ગાંઠો, જેનું મૂળ ગાંઠોથી અંતર ઓછું અથવા સમાન હોય, તે શોધી શકાય છે. જે નોડનું મૂળ નોડથી અંતર + 1 છે તે પછી શોધી શકાય છે. તેનો પેરેન્ટ નોડ છે, અને નોડ અને દ્વારા રજૂ થયેલ અક્ષર છે. (1): જો નોડનો આગળનો અક્ષર હોય, તો આ ધારનો બીજો નોડ, અને = તરીકે સેટ કરી શકાય છે. (2): જો બધા અક્ષરો અને તેના ચાઈલ્ડ નોડ્સ વચ્ચેની તમામ ધારને શોધતા ન હોય, તો તે પ્લસનો પ્રત્યય છે. કારણ કે આ પ્રત્યય મૂળ નોડ (ઉપસર્ગની જેમ) થી શરૂ થતા સ્ટ્રીંગ સાથે મેળ ખાય છે, પછી શોધી શકાય છે કે નહીં. જો નહીં, તો આ પ્રક્રિયા ત્યાં સુધી ચાલુ રાખી શકાય છે જ્યાં સુધી રુટ નોડ ન મળે. અહો-કોરાસિક શોધ અલ્ગોરિધમ મુખ્ય શબ્દ વૃક્ષમાં તમામ નિષ્ફળતા કડીઓ સ્થાપિત કર્યા પછી, અહો-કોરાસિક શોધ અલ્ગોરિધમનો ઉપયોગ રેખીય સમયમાં બધા (i = 1,2,., z) ના સ્થાનો શોધવા માટે થાય છે. આ પગલામાં, સમયની જટિલતા O (m + k) છે. અન્ય વ્યૂહરચનાઓ એમ. એસ. એ., ડી. એન. એ., આર. એન. એ. અને પ્રોટીનમાં, અનુક્રમ સામાન્ય રીતે ઉત્પન્ન થાય છે અને તેઓ ઉત્ક્રાંતિ સંબંધ ધરાવે છે તેવું માનવામાં આવે છે. આર. એન. એ., ડી. એન. એ. ના પેદા થયેલા નકશા અને ઉત્ક્રાંતિવાદી પરિવારોના ક્રમની સરખામણી કરીને, લોકો પ્રોટીનના સંરક્ષણનું મૂલ્યાંકન કરી શકે છે અને ઉત્ક્રાંતિવાદી ક્રમ વચ્ચેના તફાવતોની સરખામણી કરીને કાર્યાત્મક જનીન ક્ષેત્રો શોધી શકે છે. સામાન્ય રીતે, બહુવિધ અનુક્રમ સંરેખણ સમસ્યાઓને ઉકેલવા માટે હ્યુરિસ્ટિક અલ્ગોરિધમ્સ અને ટ્રી સંરેખણ આલેખ પણ અપનાવવામાં આવે છે. હ્યુરિસ્ટિક અલ્ગોરિધમ સામાન્ય રીતે, હ્યુરિસ્ટિક અલ્ગોરિધમ્સ પુનરાવર્તિત વ્યૂહરચના પર આધાર રાખે છે, જે કહે છે કે તુલનાત્મક પદ્ધતિ પર આધારિત છે, પુનરાવર્તિત પ્રક્રિયા દ્વારા બહુવિધ અનુક્રમ સંરેખણના પરિણામોને શ્રેષ્ઠ બનાવે છે. ડેવી એમ. એ બહુવિધ અનુક્રમ સંરેખણ સમસ્યાને ઉકેલવા માટે કણ સ્વાર્મ ઓપ્ટિમાઇઝેશન અલ્ગોરિધમનો ઉપયોગ કરવાની દરખાસ્ત કરી હતી; ઇકેડા તાકાહિરોએ હ્યુરિસ્ટિક અલ્ગોરિધમનો પ્રસ્તાવ મૂક્યો હતો જે એ * સર્ચ અલ્ગોરિધમ પર આધારિત છે; ઇ. બર્નીએ પ્રથમ બહુવિધ અનુક્રમ સંરેખણ સમસ્યાને ઉકેલવા માટે છુપાયેલા માર્કોવ મોડેલનો ઉપયોગ કરવાની દરખાસ્ત કરી હતી; અને અન્ય ઘણા જીવવિજ્ઞાનીઓ તેને ઉકેલવા માટે આનુવંશિક અલ્ગોરિધમનો ઉપયોગ કરે છે. આ તમામ અલ્ગોરિધમ્સ સામાન્ય રીતે સિક્વન્સની સંખ્યા માટે મજબૂત અને અસંવેદનશીલ હોય છે, પરંતુ તેમાં ખામીઓ પણ હોય છે. ઉદાહરણ તરીકે, પાર્ટિકલ સ્વાર્મ ઓપ્ટિમાઇઝેશન અલ્ગોરિધમમાંથી પરિણામો અસ્થિર છે અને તેની ગુણવત્તા રેન્ડમ સંખ્યાઓની પસંદગી પર આધારિત છે, એ * સર્ચ અલ્ગોરિધમનો રનટાઇમ ખૂબ લાંબો છે, અને આનુવંશિક અલ્ગોરિધમનો સ્થાનિક શ્રેષ્ઠમાં આવવો સરળ છે. વૃક્ષ સંરેખણ આલેખ આશરે, વૃક્ષ સંરેખણ આલેખનો હેતુ વૃક્ષોને આલેખમાં સંરેખિત કરવાનો અને અંતે આંકડાશાસ્ત્ર વિકસાવવા માટે તેમનું સંશ્લેષણ કરવાનો છે. જીવવિજ્ઞાનમાં, વૃક્ષ સંરેખણ આલેખ (ટી. એ. જી.) નો ઉપયોગ વૃક્ષોના સમૂહમાંથી ઉત્ક્રાંતિ સંઘર્ષો અથવા ઓવરલેપિંગ ટેક્સાને દૂર કરવા માટે થાય છે અને પછી અનિશ્ચિતતા અને સંઘર્ષને શોધવા માટે પૂછપરછ કરી શકાય છે. સંરેખિત કરવાની, સંશ્લેષણ કરવાની અને વિશ્લેષણ કરવાની પદ્ધતિઓને એકીકૃત કરીને, ટીએજીનો ઉદ્દેશ વિરોધાભાસી સંબંધો અને શ્રેણીની વિશાળ શ્રેણીમાંથી મેળવેલા આંશિક ઓવરલેપિંગ ટેક્સોન સમૂહોને ઉકેલવાનો છે. ઉપરાંત, વૃક્ષ સંરેખણ આલેખ સુપરટ્રી અને કલમ બનાવવાની કસરતો માટે મૂળભૂત અભિગમ તરીકે કામ કરે છે, જેનું બેરી દ્વારા સુપરટ્રી બનાવવા માટે સફળતાપૂર્વક પરીક્ષણ કરવામાં આવ્યું છે. કારણ કે વૃક્ષોમાંથી આલેખમાં પરિવર્તન તેમના સ્રોત વૃક્ષોમાંથી સમાન ગાંઠો અને ધાર ધરાવે છે, ટીએજી વધુ વિશ્લેષણ માટે મૂળ સ્રોત વૃક્ષોનું નિષ્કર્ષણ પણ પ્રદાન કરી શકે છે. ટીએજી એ સંરેખિત વૃક્ષોના સમૂહનું સંયોજન છે. તે વિરોધાભાસી પૂર્વધારણાઓ ઉત્ક્રાંતિ સંબંધોને સંગ્રહિત કરી શકે છે અને ઉત્ક્રાંતિ પૂર્વધારણાઓ વિકસાવવા માટે સ્રોત વૃક્ષોનું સંશ્લેષણ કરી શકે છે. તેથી, સંરેખણની અન્ય સમસ્યાઓ ઉકેલવા માટે તે એક મૂળભૂત પદ્ધતિ છે. સામાન્યીકૃત વૃક્ષ સંરેખણ સંદર્ભો કોમ્પ્યુટેશનલ ફિલોજેનેટિક્સ પણ જુઓ.