Cuprins

Construirea arborilor filogenetici

Exerciţii

Temă

Clustering bottom-up

UPGMA

(Unweighted Pair Group Method using arithmetic Averages)

Construieşte un arbore, pornind de la grupuri (clustere) cu un singur element, prin unirea a câte două grupuri de similaritate maximă (distanţă minimă).

Distanţa dintre două clustere se defineşte astfel:

d_ij = 1/(|C_i| * |C_j|) * sumj (d_pq), p in C_i, q in C_j (1)

Date două clustere Ck şi Cl , cu Ck = Ci U Cj :

d_lk = (d_il * |C_i| + d_jl * |C_j|)/(|C_i| + |C_j|) (2) 
Initializare:
  multimea clusterelor C = {}
  for i = 1..n
    C_i = {sequence_i}
    C = C U {C_i}
    defineste o frunza i pentru sequence_i, plasata la inaltime h_i=0

Iteratie:
  gaseste clusterele C_i, C_j pentru care d_ij e minima
    (in cazul cand exista mai multe astfel de perechi, se alege una aleator)
  construieste C_k = C_i U C_j
  for all C_l in C
    calculeaza d_kl
  defineste un nod k, parinte pentru i si j, 
    cu h_k = d_ij/2
  C = (C - {C_i, C_j}) U {C_k}

Terminare:
  cand raman doar doua clustere C_i si C_j,
    construieste un nod radacina la inaltimea h_r = d_ij/2

Neighbour-joining

Spre deosebire de UPGMA, construieşte arbori fără rădăcină, şi elimină presupunerea că divergenţa secvenţelor fiice a avut loc la acelaşi moment de timp (exprimată prin drumuri de lungime egală de la rădăcină la orice frunză).

La fiecare pas, se aleg cele mai apropiate două secvenţe, de data aceasta apropierea fiind exprimată nu doar in funcţie de distanţa propriu-zisă între secvenţe (care trebuie să fie cât mai mică), ci şi de media distanţelor fiecărui nod faţă de celelalte noduri (care trebuie să fie cât mai mare):

D_ij = d_ij - (r_1 + r-j) (3)

unde

r_i = (1 / (|L| - 2)) * sum(d_ik), k in L (4)
este utilizat şi la reglarea distanţei dintre nodurile fiu i, j şi părintele k. 
Initializare:
  multimea nodurilor frunza T = multimea secventelor
  L = T

Iteratie:
  alege i, j a.i. D_ij sa fie minim
  defineste un nou nod k
  for all m in L
    d_km = 1/2 * (d_im + d_jm - d_ij)
  d_ik = 1/2 * (d_ij + r_i - r_j)
  d_jk = d_ij - d_ik
  T = T U {k}, k parinte pentru i si j
  L = (L - {i, j}) U {k}

Terminare:
  cand raman doar doua noduri i si j in L,
    adauga la T muchia dintre i si j de lungime d_ij

Exerciţii

  1. [UPGMA] Demonstraţi formula (2).
  2. [UPGMA] Demonstraţi că înalţimea la care se găseşte un nod părinte este întotdeauna mai mare decât cea a fiilor săi.
  3. [UPGMA, NJ] Construiţi arborii rezultaţi prin aplicarea UPGMA, respectiv Neighbour-joining pentru secvenţele cărora le corespunde următoarele matrice de distanţe:
      A B C D E
    B 2  
    C 4 4  
    D 6 6 6  
    E 6 6 6 4  
    F 8 8 8 8 8
  4. HIV sequence database - How to make a phylogenetic tree: folosiţi interfaţa referenţiată în acest tutorial pentru a construi arbori filogenetici din secvenţe disponibile în bazele de date; analizaţi rezultatele.

Temă

Implementaţi unul dintre algoritmii UPGMA şi Neigbor-joining, la alegere. Input-ul va consta într-o matrice de distanţe între secvenţe (exemplu: HIV1, HIV2, SIV). Afişsaţi în format text, într-o manieră expresivă, arborele rezultat.

Se acordă bonus pentru implementarea ambilor algoritmi.

Se acordă bonus pentru dezvoltarea unui instrument (preferabil cu interfaţă web) care oferă reprezentare grafică a rezultatelor şi care poate fi folosit ca demo în scopuri didactice.

Resurse

  • R. Durbin et al: Biological Sequence Analysis, capitolul 7