Teiresias algoritm

Teiresias -algoritmen är en kombinatorisk algoritm för upptäckt av stela mönster (motiv) i biologiska sekvenser. Den är uppkallad efter den grekiska profeten Teiresias och skapades 1997 av Isidore Rigoutsos och Aris Floratos.

Problemet med att hitta sekvenslikheter i den primära strukturen hos relaterade proteiner eller gener uppstår vid analys av biologiska sekvenser. Det kan visas att mönsterupptäckt i dess allmänna form är NP-hårt . Teiresias-algoritmen är baserad på observationen att om ett mönster sträcker sig över många positioner och visas exakt k gånger i inmatningen måste alla fragment (undermönster) av mönstret förekomma minst k gånger i inmatningen. Algoritmen kan producera alla mönster som har ett användardefinierat antal kopior i den givna ingången, och lyckas vara mycket effektiv genom att undvika uppräkning av hela utrymmet. Slutligen rapporterar algoritmen motiv som är maximala i både längd och sammansättning.

En ny implementering av Teiresias-algoritmen gjordes nyligen tillgänglig av Computational Medicine Center vid Thomas Jefferson University . Teiresias är också tillgängligt via ett interaktivt webbaserat användargränssnitt av samma center. Se externa länkar för båda.

Mönsterbeskrivning

Teiresias-algoritmen använder reguljära uttryck för att definiera mönstren. Detta gör att de rapporterade mönstren inte bara består av tecknen som förekommer i varje position (bokstaver) utan från en specifik grupp av tecken (bokstavar inom parentes) eller till och med från vilket tecken som helst (jokertecken). Mönstren som skapas av algoritmen är <L,W>-mönster som har åtminstone k instanser i ingången, där L ≤ W och L, W, k positiva heltal. Ett mönster kallas ett <L,W>-mönster om och endast om några L på varandra följande bokstaver eller bokstaver inom parentes spänner över de flesta W-positioner (dvs. det kan inte finnas fler än WL jokertecken).

Algoritmen rapporterar endast maximala mönster. Givet en uppsättning sekvenser S, kallas ett mönster P som uppträder k gånger i S maximalt om och endast om det inte finns något mönster P' som är mer specifikt än P och uppträder också exakt k gånger i S. Om det finns ett sådant mönster P' då säger vi att P inte kan vara maximal och P anses vara subsumerad av P'. Ett mönster P' sägs vara mer specifikt än ett mönster P om och endast om P' kan erhållas från P genom att (a) hänvisa till ett jokertecken eller (b) instansiera en bokstavlig parentes till en bokstavlig, eller (c) lägga till en sträng med bokstaver, bokstaver inom parentes eller/och jokertecken till höger om P, eller (d) före en sträng med bokstaver, parenteser eller/och jokertecken till vänster om P.

Algoritmbeskrivning

Teiresias består av två faser, Scanning och Convolution. Under den första fasen skannas ingången efter de mönster som uppfyller minimikraven, de elementära mönstren. De elementära mönstren består av exakt L bokstaver och/eller bokstaver inom parentes och inkluderar högst WL jokertecken. Under faltning kombineras de elementära mönstren rekursivt och maximala mönster skapas. Ordningen i vilken faltningarna utförs är mycket viktig eftersom den garanterar att alla mönster kommer att genereras och alla maximala mönster genereras före alla mönster som ingår i dem. Ordningen dikteras av följande regler

Prioriteten för varje mönster definieras av dess innehåll från vänster till höger.
En literal har högre prioritet än en literal inom parentes och båda har högre prioritet än jokertecken (det mer specifika först).
Längre mönster har högre prioritet än kortare.
Slipsar löses alfabetiskt.

Med försäkran om att alla maximala mönster kommer att skapas först, är det lätt att kontrollera ett nyskapat mönster mot alla maximala för att säkerställa att det subsumeras, i vilket fall det kasseras. Om det nyskapade mönstret inte är subsumerat läggs det till i listan över maximala mönster. När inga fler mönster kan kombineras för att bilda nya maximala mönster avslutas algoritmen. Längden av ett maximalt mönster begränsas uppifrån av längden på den längsta inmatningssekvensen.

Tidskomplexitet

Algoritmen är "utgångskänslig". Tidskomplexiteten för TEIRESIAS-algoritmen är

$O\left(W^{L}m\log m+W(Cm+t_ {H})\summa _{P_{max}}{rc(P)}\höger)$

där L och W är användarspecificerade parametrar som definierar "minsta densitet" för ett mönster (alla L- literaler eller parenteser kan inte sträcka sig över mer än W- positioner), m är antalet tecken som inmatningen innehåller, C ≤ 1 är medeltalet av mönster som finns i en hash-post, t _H är den tid som behövs för att lokalisera hash-posten som motsvarar ett givet hashvärde, rc(P) är antalet bokstaver i P, och det kan visas som mest rc(P)-mönster kan placeras på stapeln medan du bygger P. Och summeringen Σ är det maximala antalet mönster som någonsin kommer att placeras i stapeln som behåller mönstren för förlängning under faltning.

externa länkar