Vi presenterar en systematisk behandling av anpassningsavstånd och lokala likhetsalgoritmer på träd och skogar. Vi bygger på trädjusteringsalgoritmen för beställda träd som ges av Jiang et. Al (1995) och utvidga den för att beräkna lokala skogsanpassningar, vilket är nödvändigt för att finna lokala liknande regioner i RNA sekundära strukturer. Tiden komplexitet av vår algoritm är Motivation RNA är en kedja molekyl, matematiskt en sträng över ett fyra bokstäver alfabet. Den är byggd av nukleotider som innehåller baserna A (denin), C (ytosin), G (uanin) och U (racil). Genom att vika tillbaka på sig själv bildar en RNA-molekyl struktur, stabiliserad av krafterna av vätebindningar mellan vissa par av baser (A-U, C-G, G-U), och tät stapling av angränsande baspar. Utredningen av RNA sekundära strukturer är en utmanande uppgift i molekylärbiologi. RNA-molekyler har en stor variation av funktioner i cellen som ofta beror på speciella strukturella egenskaper. Strängredigeringsavstånd [25] är helt klart den mest framgångsrika modellen i sekvensjämförelse. Det används i dokumentbehandling, filjämförelse, molekylär sekvensanalys, och många andra tillämpningar av ungefärlig strängmatchning. Grundmodellen är att en sträng "redigeras" till en annan sträng genom en sekvens av redigeringsåtgärder, såsom ersättning för enstaka tecken (R), radering (D) eller införande (I). Vikterna i samband med redigeringsåtgärder summerar upp till en total poäng, och redigeringssekvensen som ger minimal poäng definierar redigeringsavståndet för de två strängarna. På motsvarande sätt kan redigeringsprocessen, som ignorerar redigeringsordningen, representeras som en anpassning. Denna likvärdighet generaliseras inte till träd, som redan nämnts i [1]. För varje trädjustering kan man konstruera en motsvarande sekvens av redigeringsåtgärder, men inte tvärtom. Man kan förstå redigering som att hitta en största gemensam understruktur, medan anpassning innebär att hitta den minsta gemensamma överbyggnaden (I själva verket beror detta på poängsättningsschemat.). Vilken modell som är gynnsam beror på problemet. Den första generaliseringen av redigeringsmodellen från strängar till rotade beställda träd beror på [23], algoritmiskt förbättrad i [31] och implementeras och tillämpas på computa-
H€ ochsmann m.fl. REF utvecklade ett annat tillvägagångssätt för att upptäcka lokala likheter i RNA-sekundära strukturer.
Local similarity in RNA secondary structures
{'venue': 'Computational Systems Bioinformatics. CSB2003. Proceedings of the 2003 IEEE Bioinformatics Conference. CSB2003', 'journal': 'Computational Systems Bioinformatics. CSB2003. Proceedings of the 2003 IEEE Bioinformatics Conference. CSB2003', 'mag_field_of_study': ['Computer Science', 'Medicine']}