Algorytm Tejrezjasza

Algorytm Teiresiasa to algorytm kombinatoryczny służący do odkrywania sztywnych wzorców (motywów) w sekwencjach biologicznych. Został nazwany na cześć greckiego proroka Tejrezjasza i został stworzony w 1997 roku przez Izydora Rigoutsosa i Arisa Floratosa.

Problem znalezienia podobieństw sekwencji w strukturze pierwszorzędowej powiązanych białek lub genów pojawia się w analizie sekwencji biologicznych. Można pokazać, że wykrywanie wzorców w swojej ogólnej postaci jest NP-trudne . Algorytm Tejrezjasza opiera się na obserwacji, że jeśli wzorzec obejmuje wiele pozycji i pojawia się dokładnie k razy na wejściu, to wszystkie fragmenty (wzorce podrzędne) wzoru muszą występować co najmniej k razy na wejściu. Algorytm jest w stanie wytworzyć wszystkie wzorce, które mają zdefiniowaną przez użytkownika liczbę kopii na danym wejściu, i udaje mu się być bardzo wydajnym, unikając wyliczania całej przestrzeni. Wreszcie algorytm zgłasza motywy, które są maksymalne zarówno pod względem długości, jak i składu.

Nowa implementacja algorytmu Teiresiasa została niedawno udostępniona przez Centrum Medycyny Obliczeniowej na Uniwersytecie Thomasa Jeffersona . Teiresias jest również dostępny za pośrednictwem interaktywnego internetowego interfejsu użytkownika tego samego centrum. Zobacz linki zewnętrzne dla obu.

Opis wzoru

Algorytm Teiresias używa wyrażeń regularnych do definiowania wzorców. Dzięki temu zgłaszane wzorce składają się nie tylko ze znaków pojawiających się na każdej pozycji (literały), ale z określonej grupy znaków (literały w nawiasach), a nawet z dowolnego znaku (znaki wieloznaczne). Wzorce utworzone przez algorytm to wzorce <L,W>, które mają co najmniej k wystąpień na wejściu, gdzie L ≤ W i L, W, k dodatnich liczb całkowitych. Wzorzec nazywany jest wzorcem <L,W> wtedy i tylko wtedy, gdy dowolne L kolejnych literałów lub literałów w nawiasach rozciąga się na większości W pozycji (tj. nie może być więcej niż WL symboli wieloznacznych).

Algorytm raportuje tylko wzorce maksymalne. Biorąc pod uwagę zbiór sekwencji S, wzorzec P, który pojawia się k razy w S, nazywany jest maksymalnym wtedy i tylko wtedy, gdy nie istnieje żaden wzorzec P', który jest bardziej specyficzny niż P i również pojawia się dokładnie k razy w S. Jeśli istnieje taki wzorzec P', to mówimy, że P nie może być maksymalne i P uważa się za podciągnięte przez P'. Mówi się, że wzorzec P' jest bardziej specyficzny niż wzorzec P wtedy i tylko wtedy, gdy P' można uzyskać z P przez (a) wyłuskanie odniesienia do symbolu wieloznacznego lub (b) utworzenie instancji literału w nawiasie do literału lub (c) dołączenie ciąg literałów, literałów w nawiasach i/lub symboli wieloznacznych po prawej stronie P lub (d) poprzedzenie ciągu literałów, literałów w nawiasach lub/i symboli wieloznacznych po lewej stronie P.

Opis algorytmu

Tejrezjasz składa się z dwóch faz, Skanowania i Konwolucji. Podczas pierwszej fazy dane wejściowe są skanowane w poszukiwaniu wzorców spełniających minimalne wymagania, wzorców elementarnych. Wzorce elementarne składają się dokładnie z literałów L i/lub literałów w nawiasach i zawierają co najwyżej symbole wieloznaczne WL. Podczas splotu wzorce elementarne są rekurencyjnie łączone i tworzone są wzorce maksymalne. Kolejność, w jakiej wykonywane są sploty, jest bardzo ważna, ponieważ gwarantuje, że wszystkie wzorce zostaną wygenerowane, a wszystkie wzorce maksymalne zostaną wygenerowane przed wszystkimi wzorcami, które są przez nie podciągnięte. Kolejność jest podyktowana poniższymi zasadami

Priorytet każdego wzorca jest określony przez jego zawartość od lewej do prawej.
Literał ma wyższy priorytet niż literał w nawiasach i oba mają wyższy priorytet niż symbole wieloznaczne (bardziej szczegółowe jako pierwsze).
Dłuższe wzorce mają wyższy priorytet niż krótsze.
Remisy są rozstrzygane alfabetycznie.

Mając pewność, że wszystkie wzorce maksymalne zostaną utworzone jako pierwsze, łatwo jest porównać nowo utworzony wzorzec ze wszystkimi wzorcami maksymalnymi, aby upewnić się, że został on podciągnięty, aw takim przypadku zostaje odrzucony. Jeżeli nowo utworzony wzorzec nie jest podciągnięty to jest dodawany do listy wzorców maksymalnych. Kiedy nie można połączyć więcej wzorców w celu utworzenia nowych wzorców maksymalnych, algorytm kończy działanie. Długość dowolnego wzorca maksymalnego jest ograniczona od góry długością najdłuższej sekwencji wejściowej.

Złożoność czasowa

Algorytm jest „wrażliwy na dane wyjściowe”. Złożoność czasowa algorytmu TEIRESIAS wynosi

${\ Displaystyle O \ lewo (W ^ {L} m \ log m + W (Cm + t_ {H})\suma _{P_{max}}{rc(P)}\right)}$

gdzie L i W to parametry określone przez użytkownika, które definiują „minimalną gęstość” wzorca ( literały L lub nawiasy nie mogą obejmować więcej niż pozycji W ), m to liczba znaków, które zawiera dane wejściowe, C ≤ 1 to średnia liczba wzorców znalezionych we wpisie z haszem, t _H to czas potrzebny do zlokalizowania wpisu skrótu odpowiadającego dowolnej wartości skrótu, rc(P) to liczba literałów w P i można to pokazać co najwyżej wzorce rc(P) można umieścić na stosie podczas budowania P. Oraz suma Σ to maksymalna liczba wzorców, które kiedykolwiek zostaną umieszczone na stosie, który przechowuje wzorce do rozszerzenia podczas splotu.

Linki zewnętrzne