Cuprins

Construirea arborilor filogenetici

Parsimonie

Este metoda folosită pentru a calcula costul unui arbore T cu topologie cunoscută, sau pentru a căuta între toţi arborii posibili pe cel de cost minim.

Algoritmii de mai jos calculează costul pentru o singură poziţie u din secvenţele din noduri.

Traditional Parsimony

Initializare:
  costul C = 0
  nodul de start (radacina): k = 2*n + 1

Recursie - obtinerea multimii de reziduuri posibile R_k:
  if k este frunza
    R_k = x_k[u]
  else
    calculeaza R_i, R_j ale nodurilor fii i si j
    if R_i n R_j != multimea vida
      R_k = R_i n R_j
    else
      R_k = R_i U R_j
      C = C + 1

Terminare:
  costul arborelui = C
  traceback pentru identificarea rezidurilor din nodurile interne
  (se vor face alegeri arbitrate daca exista mai multe posibilitati)

Weighted Parsimony

Initializare:
  nodul de start (radacina): k = 2*n + 1

Recursie - calculul lui S_k(a):
  if k este frunza
    if a = x_k[u]
      S_k(a) = 0
    else
      S_k(a) = Infinit
  else
    calculeaza S_i(a), S_j(a) ale nodurilor fii i si j
       pentru toti a
    S_k(a) = min_b(S_i(b) + s(a, b)) + min_b(S_j(b) + s(a, b))
    pentru traceback: adauga pointeri la acele reziduri
    care minimizeaza costul
      in formula de mai sus:
      left_k(a)  = argmin_b(S_i(b) + s(a,b))
      right_k(a) = argmin_b(S_j(b) + s(a,b))

Terminare:
  costul arborelui = min_a(S_2n-1(a))
  traceback pentru identificarea rezidurilor din nodurile interne
  (se vor face alegeri arbitrate daca exista mai multe posibilitati
   cu acelasi scor minim)

Exerciţii

  1. Arătaţi că algoritmul Weighted Parsimony produce acelaşi cost ca şi Traditional Parsimony dacă S(a, a) = 0 şi S(a, b) = 1 dacă a != b.
  2. Pentru cei doi algoritmi, descrieţi procedurile de traceback care să reconstruiască asignările optimale ale caracterelor.

Resurse