Trädjustering

Inom beräkningsfylogenetik är trädanpassning ett beräkningsproblem som handlar om att producera multipla sekvensanpassningar , eller anpassningar av tre eller flera sekvenser av DNA , RNA eller protein . Sekvenser är ordnade i ett fylogenetiskt träd som modellerar de evolutionära förhållandena mellan arter eller taxa . Redigeringsavstånden mellan sekvenser beräknas för var och en av trädets interna hörn, så att summan av alla redigeringsavstånd inom trädet minimeras . Trädanpassning kan åstadkommas med en av flera algoritmer med olika avvägningar mellan hanterbar trädstorlek och beräkningsansträngning.

Definition

Indata : En uppsättning $S$ av sekvenser, ett fylogenetiskt träd $T$ lövmärkt med $S$ och en redigera avståndsfunktion d $\displaystyle d}$ mellan sekvenser.

Output : En märkning av de interna hörnen av $T$ så att $\Sigma _{e\in T}d(e)$ minimeras, där $d(e)$ är redigeringsavståndet mellan ändpunkterna för $e$ .

Uppgiften är NP-hård .

Bakgrund

Sekvensjustering

Huvudartikel: Sekvensjustering

Detta är en enkel sekvensjustering av insulingenen mellan råtta, människa och kyckling. De märkta nukleotiderna är de olika nukleotiderna med råttor I och --- betyder de saknade nukleotiderna

Inom bioinformatik är den grundläggande metoden för informationsbehandling att kontrastera sekvensdata. Biologer använder det för att upptäcka funktionen, strukturen och evolutionär information i biologiska sekvenser. Följande analyser är baserade på sekvenssammansättningen : den fylogenetiska analysen, haplotypjämförelsen och förutsägelsen av RNA- struktur. Därför kommer effektiviteten av sekvensanpassning direkt att påverka effektiviteten av att lösa dessa problem. För att designa en rationell och effektiv sekvensanpassning blir algoritmhärledningen en viktig forskningsgren inom området bioinformatik.

I allmänhet betyder sekvensjustering att man konstruerar en sträng från två eller flera givna strängar med största likhet genom att lägga till bokstäver, ta bort bokstäver eller lägga till ett mellanslag för varje sträng . Problemet med multipelsekvensanpassning är i allmänhet baserat på parvis sekvensanpassning och för närvarande, för ett parvis sekvensanpassningsproblem, kan biologer använda ett dynamiskt programmeringssätt för att erhålla dess optimala lösning. Emellertid är problemet med multipelsekvensanpassning fortfarande ett av de mer utmanande problemen inom bioinformatik. Detta beror på att hitta den optimala lösningen för multipelsekvensinriktning har bevisats som ett NP-komplett problem och endast en ungefärlig optimal lösning kan erhållas.

Avståndsmatrismetod

Avståndsmetoden mäter det minsta antalet teckeninsättningar, raderingar och substitutioner som krävs för att transformera en sekvens u till den andra sekvensen v när de används på ett par strängar. Beräkningen av redigeringsavstånd kan baseras på dynamisk programmering , och ekvationen är i O(|u|×|v|) tid, där |u| och |v| är längderna på u och v. Den effektiva uppskattningen av redigera avstånd är väsentlig eftersom avståndsmetoden är en grundläggande princip i beräkningsbiologin För funktioner av ärftliga egenskaper kan "symmetrisering" användas. På grund av en rad funktioner som används för att beräkna redigeringsavstånd, kan olika funktioner resultera i olika resultat. Att hitta en optimal redigeringsavståndsfunktion är avgörande för trädjusteringsproblemet.

Problemet med trädanpassning

Denna siffra anger tillväxthastigheten kring exponentialtiden, polynomtiden och linjärtiden

Trädjustering resulterar i ett NP-hårt problem, där poänglägen och alfabetstorlekar är begränsade. Den kan hittas som en algoritm, som används för att hitta den optimerade lösningen. Det finns dock ett exponentiellt samband mellan dess effektivitet och talsekvenserna, vilket innebär att när längden på sekvensen är mycket stor, är beräkningstiden som krävs för att få resultat enormt lång. Att använda stjärnjustering för att få den ungefärliga optimerade lösningen är snabbare än att använda trädjustering. Oavsett graden av likhet med flera sekvenser, har tidskomplexiteten för stjärninriktningen ett proportionellt samband med kvadraten på sekvensnumret och kvadraten på sekvensens medellängd. Som vanligt är sekvensen i MSA så lång att den också är ineffektiv eller till och med oacceptabel. Därför är utmaningen att reducera tidskomplexiteten till linjär en av kärnfrågorna vid trädanpassning.

Kombinatorisk optimeringsstrategi

Kombinatorisk optimering är en bra strategi för att lösa MSA-problem. Idén med kombinatorisk optimeringsstrategi är att transformera multipelsekvensinriktningen till parsekvensinriktning för att lösa detta problem. Beroende på dess transformationsstrategi kan den kombinatoriska optimeringsstrategin delas in i trädanpassningsalgoritmen och stjärnanpassningsalgoritmen. För en given flersekvensuppsättning $S$ ={ $s_{1}$ ,..., $s_{n}$ }, hitta ett evolutionärt träd som har n blad noder och etablera ett till ett förhållande mellan detta evolutionära träd och uppsättningen $S$ . Genom att tilldela sekvensen till de interna noderna i det evolutionära trädet, beräknar vi den totala poängen för varje kant, och summan av alla kanternas poäng är poängen för det evolutionära trädet. Syftet med trädanpassning är att hitta en tilldelad sekvens, som kan få en maximal poäng, och få det slutliga matchningsresultatet från det evolutionära trädet och dess noders tilldelade sekvens. Stjärninriktning kan ses som ett specialfall av trädinriktningen. När vi använder stjärninriktning har det evolutionära trädet bara en intern nod och n lövnoder. Sekvensen, som är tilldelad den interna noden, kallas kärnsekvensen.

Nyckelordsträdsteorin och Aho-Corasick-sökalgoritmen

När den kombinatoriska optimeringsstrategin används för att transformera multipelsekvensinriktningen till parsekvensinriktning, ändras huvudproblemet från "Hur man förbättrar effektiviteten av multipelsekvensanpassning" till "Hur man förbättrar effektiviteten av parvis sekvensanpassning." Keyword Tree Theory och Aho-Corasick-sökalgoritmen är ett effektivt tillvägagångssätt för att lösa problemet med parvis sekvensanpassning. Syftet med att kombinera nyckelordsträdsteorin och Aho-Corasick-sökalgoritmen är att lösa denna typ av problem: för en given lång sträng $T$ och en uppsättning korta strängar $P$ ={ $p_{1}$ , $p_{2}$ ,... , $p_{z}$ } (z∈N,z>1), hitta platsen för alla $P_{i}$ i $T$ . Nyckelordsträdet som produceras av uppsättningen $P$ används och söks sedan efter i $T$ med detta nyckelordsträd genom Aho-Corasick-sökalgoritmen. Den totala tidskomplexiteten för att använda denna metod för att hitta alla ${\displaystyle P_{i}}:$ s positioner i T är O( $m$ + $n$ + $k$ ), där $m$ =| $T$ | (längden på $T$ ), $n$ =Σ| $P_{i}$ | (summan av alla $P_{i}$ s längder) och $k$ betyder summan av förekomsten för alla $P_{i}$ i $T$ .

Nyckelordsträdteori

Nyckelordsträdet för uppsättningen $P$ ={ $p_{1}$ , $p_{2}$ ,... , $p_{z}$ } (z∈N,z>1) är ett rotat träd, vars rot betecknas med K, och detta nyckelordsträd uppfyller:

(1): Varje kant avgränsar tydligt en bokstav.

(2): Alla två kanter separerade från samma nod ska motsvara olika bokstäver.

(3) Varje mönster $P_{i}$ (i=1,2,...,z) motsvarar en nod $v$ , och vägen från roten K till noden $v$ kan stava strängen ${\displaystyle P_{i}} exakt korrekt$ .

För varje lövnod i detta K-träd motsvarar den ett av de vissa mönstren i uppsättningen $P$ .

$L(v)$ används för att representera STRING som är ansluten från rotnoden till noden $v$ . $Lp(v)$ kommer sedan att användas för att representera längden på det längsta suffixet (även detta suffix är prefixet för ett av mönstren i uppsättningen $P$ ). Söker efter detta prefix från rotnoden i nyckelordsträdet och den sista noden betecknad med $n_{v}$ när sökningen är över.

Till exempel visas uppsättningen $P$ ={potatis, tatuering, teater, annat} och nyckelordsträdet till höger. I det exemplet, om $L(v)$ =potat, då $Lp(v)$ =|tat|=3, och fellänken för noden ${ \displaystyle v}$ visas i den bilden.

Att upprätta en fellänk är nyckeln till att förbättra tidskomplexiteten hos Aho-Corasick-algoritmen. Den kan användas för att reducera den ursprungliga polynomtiden till den linjära tiden för sökning. Därför är kärnan i nyckelordsträdsteorin att hitta alla fellänkar (vilket också innebär att hitta alla $n_{v}$ s) i ett nyckelordsträd i den linjära tiden. Det antas att varje $n_{v}$ av alla noder $v$ , vars avstånd från rotnoden är mindre än eller lika med $k$ , kan hittas. n $n_{v}$ för noden $v$ vars avstånd från rotnoden är $k$ + 1 kan sedan sökas efter Dess överordnade nod är $v'$ , och bokstaven som representeras av noden $v$ och $v'$ , är $x$ .

(1): Om nästa bokstav i noden $n_{v}'$ är $x$ , kan den andra noden i denna kant ställas in som $w$ , och $n_{v}$ = $w$ .

(2): Om alla bokstäver inte är $x$ genom att söka i alla kanter mellan $n_{v}'$ och dess underordnade noder, $L(n_{v })$ är ett suffix av $L(n_{v}')$ plus $x$ . Eftersom detta suffix matchar STRING som börjar med rotnoden (liknande prefix), $x$ efter $n_{v}'$ detekteras eller inte. Om inte, kan denna process fortsätta tills $x$ eller rotnoden hittas.

Aho-Corasick sökalgoritm

Huvudartikel: Aho–Corasick strängmatchningsalgoritm

Efter att ha upprättat alla fellänkar i nyckelordsträdet, används Aho-Corasick-sökalgoritmen för att hitta platserna för alla $P_{i}$ (i=1,2,...,z) i linjären tid. I detta steg är tidskomplexiteten O(m+k).

Andra strategier

Huvudartikel: Multipelsekvensjustering

I MSA, DNA, RNA och proteiner genereras vanligtvis sekvenser och de antas ha ett evolutionärt samband. Genom att jämföra genererade kartor över RNA, DNA och sekvenser från evolutionära familjer kan människor bedöma bevarande av proteiner och hitta funktionella gendomäner genom att jämföra skillnader mellan evolutionära sekvenser. I allmänhet används också heuristiska algoritmer och trädanpassningsgrafer för att lösa multipla sekvensanpassningsproblem.

Heuristisk algoritm

Huvudartikel: Heuristic (datavetenskap)

Generellt sett förlitar sig heuristiska algoritmer på den iterativa strategin, det vill säga den baserat på en jämförelsemetod, som optimerar resultaten av multipelsekvensinriktning genom den iterativa processen. Davie M. föreslog att använda partikelsvärmoptimeringsalgoritmen för att lösa problemet med multipelsekvensanpassning; Ikeda Takahiro föreslog en heuristisk algoritm som är baserad på A*-sökalgoritmen ; E. Birney föreslog först att använda den dolda Markov-modellen för att lösa problemet med multipelsekvensanpassning; och många andra biologer använder den genetiska algoritmen för att lösa det. Alla dessa algoritmer är generellt robusta och okänsliga för antalet sekvenser, men de har också brister. Till exempel är resultaten från partikelsvärmoptimeringsalgoritmen instabila och dess fördelar beror på valet av slumptal, körtiden för A*-sökalgoritmen är för lång och den genetiska algoritmen är lätt att falla in i lokal excellent.

Graf för trädjustering

Grovt sett syftar trädjusteringsgrafen till att anpassa träd till en graf och slutligen syntetisera dem för att utveckla statistik. Inom biologin används trädanpassningsdiagram (TAG) för att ta bort evolutionära konflikter eller överlappande taxa från uppsättningar av träd och kan sedan frågas för att utforska osäkerhet och konflikter. Genom att integrera metoder för att anpassa, syntetisera och analysera, syftar TAG till att lösa de motstridiga relationerna och partiella överlappande taxonuppsättningar som erhålls från ett brett spektrum av sekvenser. Trädjusteringsdiagrammet fungerar också som ett grundläggande tillvägagångssätt för superträd och ympningsövningar , som har testats framgångsrikt för att konstruera superträd av Berry. Eftersom omvandlingen från träd till en graf innehåller liknande noder och kanter från deras källträd, kan TAG:er också tillhandahålla extraktion av ursprungliga källträd för vidare analys. TAG är en kombination av en uppsättning justeringsträd. Det kan lagra motstridiga hypoteser evolutionära relationer och syntetisera källträden för att utveckla evolutionära hypoteser. Därför är det en grundläggande metod för att lösa andra uppriktningsproblem.

Se även

• Generaliserad trädanpassning