Bioinformatica — Laboratorul 10

Curs | Index

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10

Cuprins

Large Parsimony Problem

Large Parsimony Problem

Branch and bound

Fie multimea de secvente (frunze) disponibile {x1, ... , xn};
Se porneste cu un arbore fara radacina format din nodurile {x1, x2, x3} (muchiile sunt de asemenea numerotate):
```
      x1
      |
      |1
     / \
    /2  \3
   x2   x3
```
Se mentine un vector de indecsi [i(3), i(5), i(7), ..., i(2n-5)], cu urmatoarea semnificatie:
- indexul de pe pozitia k va indica pe care muchie va fi inserat nodul k+3 (evident se incepe expandarea arborelui cu nodul 4, deoarece 1-3 sunt deja in arbore)
  Exemplu: pentru vectorul de indecsi [3, 0, ..., 0], arborele partial este:
```
      x1
      |
      |1
     / \4 5
    /2  \---x4   
   x2   3\
         x3
```
- numarul atasat indexului (de exemplu, i(3) indica valoarea maxima pe care o poate lua acesta (fiind egal cu numarul de muchii existente in arborele partial construit pana la momentul curent)
- daca un index este 0, atunci nodul respectiv nu este in arbore; in plus, toti indecsii de la dreapta trebuie sa fie de asemenea 0, deoarece nu se poate insera un nod pe o muchie inexistenta
- trecerea celui mai din dreapta index de la 0 la 1 va trebui sa fie insotita de trecerea tuturor indecsilor nuli din stanga sa de la 0 la 1, pentru a evita astfel de muchii nedefinite
Generarea topologiilor posibile se face prin numarare:
- Se porneste cu configuratia [1, 0, ...., 0]
- Cat timp nu s-a terminat enumerarea:
  - Se evalueaza costul arborelui (partial) curent;
  - daca este mai mare decat cel mai bun cost obtinut pana la pasul curent, atunci se abandoneaza generarea arborilor din arborele partial curent, prin incrementarea celui mai din dreapta contor diferit de 0 (evident, adaugarea unei muchii nu poate decat sa mareasca costul);
  - altfel
    - daca nu s-a atins marginea superioara a ultimului index, se incrementeaza
    - altfel se trece indexul pe 0 si se incrementeaza indexul dinaintea lui, in limita marginii; depasirea va cauza anularea acestui index si incrementarea anteriorului, recursiv
Rezultat: topologia cu cel mai mic cost