Autor: David Sebastian Emil [612555]

Universitatea din Craiova. Facultatea de Științe
Departamentul de Informatică
Lucrare de Licență
Metode de grupare a datelor cu aplicații în
filogenie
Autor: David Sebastian Emil
Coordonator: Conf. Dr. Boldea Costin-Radu
Craiova 2019

Cuprins
1 Motivația temei 3
2 Evoluția moleculară 8
2.1 Principiile evoluției moleculare . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Mutațiile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Cauzele schimbării în gene allele . . . . . . . . . . . . . . . . . 9
2.1.3 Studiul molecular al filogeniei . . . . . . . . . . . . . . . . . . 10
2.2 Forțele conducătoare ale evoluției . . . . . . . . . . . . . . . . . . . . 11
2.3 Istoricul acestei științe . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Evoluția genomilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.1 Dimensiunea genomului . . . . . . . . . . . . . . . . . . . . . 13
2.4.2 Genomul procariot . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.3 Genomul eucariot . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Domenii corespunzătoare . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Modelarea evoluției 15
3.1 De la distanțe la arbori . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Algoritmi de construire a arborilor . . . . . . . . . . . . . . . . . . . 17
3.2.1 UPGMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1

3.2.2 Neighbor-Joining (unirea valorilor vecine) . . . . . . . . . . . 19
3.3 Parsimonia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.1 Procesul de înregistrare . . . . . . . . . . . . . . . . . . . . . . 22
3.3.2 Procesul de urmărire . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.3 Metoda de bootstrap (implementare prin etape succesive) . . . 23
3.4 Parsimonia maximală (filogenetică) . . . . . . . . . . . . . . . . . . . 24
3.4.1 Datele de tip caracter . . . . . . . . . . . . . . . . . . . . . . . 26
3.4.2 Procesul de selecție a speciilor . . . . . . . . . . . . . . . . . . 29
3.4.3 Analiza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4.4 Probleme în estimarea filogeniei parsimoniei maximale . . . . 36
3.4.5 Critici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4.6 Metode alternative . . . . . . . . . . . . . . . . . . . . . . . . 40
4 Aplicatie concretă: implementarea unui algoritm de determinare a
arborilor filogenetici 48
5 Concluzii 57
2

Capitolul 1
Motivația temei
Studiile filogenetice au drept scop reconstruirea istoriei evolutive a organismelor
vii. Termenul de filogenie (phylogen¯ ese) provenit de la cuvintele grecești “phulon” –
rasă și “genetikos”, “genesis” – origine, a fost introdus de către Haeckel în 1860, care
l-a definit ca fiind “istoria dezvoltării paleontologice a organismelor prin analogie
cu istoria dezvoltării individuale”. Mult timp, construcția arborilor filogenetici s-
a bazat pe folosirea caracterelor morfologice, anatomice și paleontologice. Primul
arbore filogenetic al vertebratelor, stabilit de Zuckerkandl și Pauling (1960) folosind
date moleculare, este aproape identic cu cel obținut utilizând caracterele clasice. O
dată cu evoluția tehnicilor de biologie moleculară și cu punerea la punct a tehnicii
de secvențializare de către Sanger în 1977, s-a produs o adevărată revoluție privind
utilizarea secvențelor ADN în filogenie, deoarece s-a considerat că acizii nucleici sunt
mult mai informativi decât proteinele.
Analiza secvențelor nucleotidice ale perechilor de gene omoloage furnizează infor-
mații mai complete decât secvențele în aminoacizi ale proteinelor corespunzătoare,
datorită degenerescenței codului genetic. De asemenea, ca urmare a utilizării pe
scară largă a tehnicii de amplificare PCR, materialul genetic poate fi foarte ușor
3

multiplicat și secvențializat. Introducerea acestor noi tehnici poate fi considerată
etapa cheie care a determinat o dezvoltare fulminantă a studiilor de filogenie molecu-
lară. Producerea, publicarea și introducerea unui număr mare de secvențe genetice
în bazele de date internaționale au dus la dezvoltarea bioinformaticii aplicate acestui
domeniu, materializată printr-o ofertă largă de programe necesare alinierii și analizei
secvențelor și construirii arborilor filogenetici.
Evoluția realizată prin selecția naturală a cauzat modificarea speciilor populației
prin trei mecanisme principale: schimbarea populației într-un timp evolutiv și îm-
părțirea acesteia în mai multe ramuri, hibridizarea a două specii anterioare diferite
într-una singură, sau sfârșitul populației prin distrugerea ei. Încă de când a apă-
rut viață pe această planetă, au evoluat foarte multe specii distincte înrudite între
ele. Filogenetica se ocupă cu studiul caracterelor evolutive înrudite ale speciilor și
populațiilor. Filogenia tradițională tratează modul în care speciile evoluează, încă
de la apariția datelor despre genomi, pornind de la cele fiziologice (structura osoasă
de la fosile, etc). Vom aborda filogenetica dintr-o perspectivă diferită: vom analiza
date de secvențe ADN pentru a determina relațiile dintre și între specii. În esență,
dorim să evidențiem selecția naturală în populații. Această zonă de studiu din bi-
ologia computațională devine din ce în ce mai importantă, cu aplicații comerciale
în domeniul genomicii. Recent, s-a stabilit ca o companie afiliată MIT&Harvard să
secvențializeze genomi individuali pentru suma de 5000 de dolari.
Vom aborda această problemă de biologie în termeni computaționali, studiind
două modele probabilistice de divergență: Jukes-Cantor și Kimura. Vom discuta
despre doi algoritmi, UPGMA și Neighbor-Joining, ce construiesc specii sau arbori
de gene din aceste date relaționale. Vom explica, în continuare, diferența dintre
specii și arborii de gene.
Printre multe alte probleme deschise din domeniul filogeneticii, ce se pot rezolva
4

cu ajutorul genomicii, mai apar și altele: cât de mult se aseamănă două specii, ce
metode de migrare au folosit primii oameni atunci când au părăsit continentul afri-
can, și găsirea speciei din care a evoluat omul (cimpanzeii sau gorilele), dar și multe
altele. Foarte multe probleme fără răspuns din biologia evolutivă au fost descifrate
și rezolvate de filogenetica genomică. Una din aceste probleme este reprezentată de
revelația găsirii că cel mai apropiat animal înrudit cu balena este hipopotamul.
În filogenetică, informația este reprezentată cel mai bine cu ajutorul arborilor,
aceștia arătând, în detaliu, legăturile dintre specii sau dintre gene. Există probleme
importante legate de necesitatea filogeniei atunci când evoluția este simulată cu
ajutorul arborilor, acestea fiind:
•nodurile ce unesc ramurile arborelui (tipul precis de ascendenți comuni);
•semnificația lungimilor ramurilor (măsurate sau nu în timp);
•tipul de împărțire a ramurilor arborelui (de obicei, este împărțire binară).
Ca o informație adițională la a treia chestiune de mai sus, profesorul Pavel Pevz-
ner, membru UCSD, a menționat că ordinea convergenței la problema dacă oamenii
sunt mai apropiați de câini sau de șoareci, necesită un model de trifurcație (o îm-
părțire în trei moduri).
Este important să observăm că genele și speciile sunt două evenimente distincte.
Aceeași genă (sau ușoara deformație a ei) se poate găsi în specii diferite, adică în
organisme care nu se pot încrucișa. Gândindu-ne într-un alt mod, un arbore de
specii este un caz particular de arbore de gene ce cuprinde o secvență de aceleași
gene comune. Mai mult, într-un arbore de specii poate exista un flux de gene între
diferite ramuri ale arborelui. Dacă fiecare “frunză” este un organism, atunci arborele
este un arbore de specii. Un arbore de gene cuprinde atât formarea descendentă
5

de specii noi cât și dublarea lor, lungimea dintre rădăcină și frunze reprezentând
numărul de mutații dintre cele două. Ordinul complexității arborelui (ramificația
lungimilor și numărul de mutații) arată ce tipuri de algoritmi trebuie folosiți. În
acest studiu, ne concentrăm pe compararea secvențelor, pentru a construi arbori de
gene și arbori de specii.
În filogenetică, folosirea genomilor duce la multe avantaje. Un avantaj important
este cantitatea mare de informații la care avem acces. Să considerăm, pe moment, că
pentru fiecare poziție din genom, în special pentru pozițiile individuale aminoacide
din secvența de proteine, i se asociază o caracteristică unică. De obicei, se folosesc
puține particularități pentru construirea arborilor de specii. De exemplu, în filo-
genetica tradițională (înainte de apariția datelor genomice), structura scheletică a
urșilor panda se putea compara cu cea a altor urși și a ratonilor. Premisa de bază în
crearea arborilor cu ajutorul trăsăturilor este reprezentată de principiul parsimoniei:
găsirea unui arbore ce descrie perfect mulțimea caracteristicilor într-un șir minim
de schimbări. Din păcate, mai există și cazuri complicate în care aceste trăsături nu
au un comportament normal: sunt frecvente mutațiile cu sens invers (de exemplu,
unghiile devin scurte, apoi lungi, ca apoi să ajungă scurte), neputința de a accesa
secvențele anterioare și dificultăți în corelarea ratei de substituție cu timpul. Da-
torită mutațiilor cu sens invers, chiar dacă se consideră că evoluția este divergentă
ducând la creșterea entropiei, sunt și situații în care evoluția converge (sau există
neomologia). Neomologia este fenomenul în care doi descendenți separați, complet
independenți unul de celălalt, trec prin aceleași schimbări care îi duc la convergență.
Acest proces este strict aleator și rareori a fost observat.
Să luăm, de exemplu, populația umană: încă de când specia noastră a plecat
de pe continentul african, rata mutației din cadrul genomului uman pare a fi de-
venit un eveniment filogenetic. Mutațiile sunt rare, cel mult 1000 de mutații (sau
6

polimorfisme cu o singură nucleotidă, sau SNP) într-un total de trei miliarde de
genomi cu nucleotide. Acesta este motivul pentru care sunt realizate hărți de arbori
genealogici, datorită flexibilității acestei complexități.
Genele sunt produse prin două mecanisme principale:
1.duplicarea: noi versiuni de gene vechi (este procesul cel mai frecvent);
2.gene noi: segmente de gene (ce decodifică), sau o conexiune de secvențe de
codificare (nucleotide funcționale), acestea apărând mai rar.
Vom studia trei tipuri de arbori: un arbore de specii, acestea având trăsături co-
mune, provenind de la o singură specie, frunzele arborelui reprezentând specii diferite
(cladogramă); un arbore filogenetic sau evolutiv ce reprezintă numărul schimbărilor
caracterelor prin lungimile ramurilor sale, neavând rădăcină (filogramă); și un arbore
ultrametric. Aceste trei tipuri de arbori asociază diferite sensuri lungimilor ramu-
rilor, în ordinea în care apar: niciun înțeles, schimbare genetică și timpul parcurs.
Speciile cu o durată de exploatare mult mai mică și cu perioade de reproducere mai
mari au tendința de a arăta schimbări genetice mult mai mari (de exemplu, genele
de la șoareci și cele umane). Metodele de construire a arborilor pot fi realizate prin
decuplarea noțiunii algoritmului folosit și a definiției condiției de optimalitate. De
exemplu, algoritmii de clusterizare nu au niciun criteriu de optimalitate, ei nema-
ximizând sau neminimizând funcția obiectivă. În bioinformatică, apare o dilemă:
putem să creăm un algoritm ce rezolvă bine problema dată, sau putem să creăm un
model mai potrivit (de exemplu, cum pot fi folosite schimbările frecvent observate
într-o secvență, pentru a indica o distanță către o altă secvență).
7

Capitolul 2
Evoluția moleculară
În mare parte, evoluția moleculară este un proces de evoluție la nivelul ADN-ului,
ARN-ului și al proteinelor. Evoluția moleculară a apărut în anii 1960, ca un dome-
niu științific, atunci când cercetătorii din biologia moleculară, biologia evolutivă și
din genetica populației au căutat să înțeleagă structura și funcția acizilor nucleici
și ale proteinelor. Unele din subiectele cheie ce au grăbit dezvoltarea acestui dome-
niu au fost evoluția funcției enzimelor, folosirea divergenței acidului nucleic ca un
“ceas molecular” pentru studiul divergenței speciilor, precum și originea ADN-ului
decodificant.
Progresul recent în domeniul genomicii, incluzând secvențierea întregului genom,
caracterizarea puterii de trecere a proteinei și bioinformatica, a condus la o creștere
dramatică a studiilor referitoare la această problemă. În anii 2000, unele subiecte de
dispută au fost: duplicarea genelor în scopul apariției noii funcții de gene, extinderea
evoluției adaptive moleculare versus procesele neutre de mutație și de deplasare, pre-
cum și identificarea schimbărilor moleculare responsabile ale caracteristicilor umane
diferite, în special cele aferente infecțiilor, bolilor și percepțiilor.
8

2.1 Principiile evoluției moleculare
2.1.1 Mutațiile
Mutațiile sunt schimbări permanente și transmisibile materialului genetic (de
obicei, ADN sau ARN) al unei celule. Mutațiile rezultă din copierea erorilor în ma-
terialul genetic în timpul diviziunii celulare, și din expunerea la radiații, la chimicale
sau la viruși, sau se pot întâmpla în mod deliberat în cadrul unui control celular, în
timpul unor procese, cum ar fi meioza sau hipermutația. Mutațiile sunt considerate
a fi forța conducătoare a evoluției, unde cele mai puțin favorabile (sau dăunătoare)
sunt înlăturate din gene prin selecție naturală, în timp ce mutațiile mai mult favora-
bile (sau avantajoase) tind să se înmulțească. Mutațiile neutre nu afectează șansele
organismului de supraviețuire în mediul său natural înconjurător, și, în timp, se pot
înmulți, ceea ce duce la un evident echilibru. Aceasta este interpretarea modernă a
teoriei evolutive clasice.
2.1.2 Cauzele schimbării în gene allele
Există patru procese cunoscute ce dereglează existența unei caracteristici; sau,
mai exact, o genă allele (o variantă de gene) apare cu regularitate:
•Deplasarea genetică descrie schimbările făcute în frecvența genei, ce nu pot
fi atribuite constrângerilor selective, dar sunt datorate evenimentelor aferente
particularităților moștenite. Acest fapt devine important în populațiile scăzute
ce, pur și simplu, nu au urmași suficienți pentru a-și distribui aceleași gene,
așa cum sunt generațiile de părinți.
•Fluxul de gene, Migrația, sau amestecul de gene este singurul factor ce face ca
populațiile să fie mai apropiate din punct de vedere genetic, în timp ce crează
9

mulțimi mari de gene.
•Selecția în selecție naturală particulară produsă de mortalitatea și fertilitatea
diferențială. Mortalitatea diferențială reprezintă rata de supraviețuire a in-
divizilor înainte de vârsta lor de reproducere. Dacă indivizii supraviețuiesc,
atunci ei sunt selectați cu ajutorul fertilității diferențiale, ceea ce reprezintă
contribuția lor genetică totală în următoarea generație. În acest mod, supra-
viețuitorii contribuie cu gene allele la toată mulțimea de gene, ceea ce va duce
la creșterea numărului de gene allele. De asemenea, mai sunt importante și
selecția în funcție de sex, adică atracția dintre parteneri cauzată de două gene,
una pentru o particularitate, iar cealaltă determinând o preferință pentru acea
particularitate.
•Mutația recurentă poate crește numărul de gene allele mutante.
2.1.3 Studiul molecular al filogeniei
Sistematica moleculară este un produs al sistematicii tradiționale și al geneticii
moleculare. Folosește informații pe baza constituției moleculare a ADN-ului și ARN-
ului organismelor biologice pentru a rezolva probleme în sistematică, adică să le
clasifice corect și științific din punctul de vedere al biologiei evolutive.
Sistematica moleculară a fost posibilă datorită disponibilității tehnicilor de sec-
vențializare a ADN-ului, ce a determinat secvența exactă a nucleotidelor sau a ba-
zelor din ADN și ARN. În prezent, procesul de secvențializare a întregului genom
dintr-un organism durează foarte mult și este și costisitor, acesta realizându-se nu-
mai pe câteva specii. Totuși, se poate determina secvențializarea unei anumite zone
dintr-un cromozom particular. Analizele moleculare sistematice și tipice necesită
secvențializarea a 1000 de perechi de baze.
10

2.2 Forțele conducătoare ale evoluției
În funcție de importanța relativă atribuită forțelor evolutive diferite, afirmațiile
evolutive din evoluția moleculară sunt date de trei perspective:
-Ipoteze selecționiste: deși recunoaște importanța deplasărilor aleatoare din cadrul
mutațiilor silențioase, această ipoteză admite că selecția normală și pozitivă re-
prezintă forța conducătoare a evoluției moleculare. Aceste ipoteze se bazează,
deseori, pe selecția naturală (panselecționism), ideea că această selecție este
singura forță suficient de puternică pentru explicarea evoluției, minimizând
deplasările și mutațiile aleatoare.
-Ipoteze neutraliste: acestea accentuează importanța mutațiilor, a selecțiilor de
purificare și a deplasărilor genetice aleatoare. Atât începuturile teoriei neu-
tre, scrisă de Kimura, cât și descoperirile în acest domeniu de către King și
Juke, au condus la relevanța neodarwinismului la nivelul moleculei. Teoria ne-
utră a evoluției moleculare afirmă că majoritatea mutațiilor sunt dăunătoare
și sunt repede îndepărtate prin selecția naturală, dar printre mutațiile rămase,
majoritatea sunt neutre datorită fitness-ului, în timp ce mutațiile favorabile
devin din ce în ce mai puține. Mutațiile neutre sunt determinate de deviați-
ile genetice, acestea contribuind atât la polimorfismul nucleotidelor, cât și la
diferențele dintre specii.
-Ipoteze mutaționiste: accentuează deviațiile și bazele aleatoare în cadrul mutați-
ilor. Sueoka a fost primul cercetător care a propus o abordare mutaționistă
modernă. El a afirmat că variația conținutului GC nu a fost cauzată de selecția
pozitivă, ci de constrângerile GC mutaționale.
11

2.3 Istoricul acestei științe
Evoluția moleculară a apărut la începutul secolului al XX-lea, împreună cu “bi-
ochimia comparativă”, însă domeniul acestei științe a devenit unul auto-stătător
în anii 1960-1970, imediat după apariția biologiei moleculare. Apariția secvențierii
proteinelor le-a permis biologilor să creeze domeniul filogeniei, bazându-se pe com-
pararea secvențelor, și să folosească diferențele dintre secvențele omoloage, pe bază
de ceas molecular, cu scopul de a estima perioada de timp de la ultimul ascendent
comun. La sfârșitul anilor 1960, teoria neutralistă a evoluției moleculare s-a dove-
dit ca o bază teoretică pentru ceasul molecular, deși atât teoria neutralistă cât și
ceasul molecular încă erau subiecte de controversă, deoarece majoritatea biologilor
evoluționari credeau în panselecționism, privind selecția naturală ca singurul factor
important din evoluție. După anii 1970, secvențierea acidului nucleic a permis ca
evoluția moleculară să treacă deasupra proteinelor, până la secvențele ribozonale
ARN, ce reprezintă baza de reconceptualizare a primelor perioade ale vieții.
Cadrul de lucru teoretic pentru sistematica moleculară s-a dezvoltat în 1960, în
studiile lui Emile Zuckerkandl, Emanuel Margoliash, Linus Pauling și Walter M.
Fitch. Aplicațiile sistematicii moleculare au fost începute de Charles G. Sibley (la
păsări), de Herbert C. Dessauer (la reptile) și de Morris Goodman (la primate),
urmați de Allan C. Wilson, Robert K. Selander și de John C. Avise. În 1956, s-a
început lucrul cu electroforeza proteinelor. Deși nu au fost multe rezultate care să fi
îmbunătățit clasificarea morfologică, foarte greu au rezultat indicii pentru care no-
țiunile lung durabile de clasificare a păsărilor aveau nevoie de revizuiri substanțiale.
În perioada 1974-1986, hibridizarea ADN-ADN a devenit tehnica predominantă a
cercetărilor.
12

2.4 Evoluția genomilor
Evoluția genomică este o mulțime de fenomene ce schimbă structura unui genom
în timpul evoluției acestuia.
Studiul evoluției genomului implică multe domenii, cum ar fi: analiza structurală
a genomului, studiul paraziților genomici, duplicațiile genelor și ale genomilor vechi,
poliploidele și genomica comparativă. Există cinci întrebări specifice pe care biologii
evoluționari și le adresează, cu privire la evoluția genomului:
1.Cum a evoluat genomul până la mărimea lui actuală?
2.Din ce este conținut genomul (conținut util sau inutil)?
3.Cum se distribuie genele într-un genom?
4.Din ce sunt compuse nucleotidele din genom?
5.Cum se dezvoltă decodificarea codului genetic?
2.4.1 Dimensiunea genomului
Dimensiunea genomului este reprezentată de întreg ADN-ul ce formează geno-
mul. Un genom este cuprins din regiuni genetice și regiuni pentru decodificare.
Regiunile genetice codifică proteinele, în timp ce regiunile pentru decodificare se
referă la promotori și la ADN-ul inutil. Dimensiunea genomului se mai scrie ca va-
loarea C. În cadrul unei specii, valoarea C nu se prea modifică, dar există o diferență
semnificativă între valorile C dintre specii.
13

2.4.2 Genomul procariot
Procariotele sunt organisme celulare ce conțin organite fără membrană, lipsindu-
le un nucleu structural distinct. Studiul genomului procariot arată că există o co-
relare importantă și pozitivă între valoarea C a procariotelor și cantitatea de gene
ce compune genomul. Astfel, dimensiunea genei reprezintă factorul principal în
influențarea dimensiunii genomului.
2.4.3 Genomul eucariot
În organismele eucariote, apare un paradox, acela că numărul de gene ce formează
genomul nu este același cu dimensiunea lui. Cu alte cuvinte, dimensiunea genomului
este mult mai mare față de numărul total de gene de codificare a proteinelor.
2.5 Domenii corespunzătoare
Un domeniu important în studiul evoluției moleculare îl reprezintă folosirea da-
telor moleculare pentru determinarea clasificării biologice corecte a organismelor.
Acest domeniu se numește sistematica moleculară sau filogenetica moleculară.
În studiul evoluției moleculare, s-au dezvoltat unelte și concepte folosite pentru
genomica comparativă și genetica moleculară, pe lângă faptul că fluxul de date noi
din aceste domenii au dus la îmbunătățirea evoluției moleculare.
14

Capitolul 3
Modelarea evoluției
Înainte de a construi un arbore, avem nevoie de o metodă pentru măsurarea peri-
oadelor evolutive astfel încât să poată fi construită o matrice a distanțelor. Această
matrice va permite schimbarea unei mulțimi de secvențe într-o mulțime de perechi
de distanțe între secvențe. Vom folosi două tipuri de mutații cu o singură nucleo-
tidă: transformări (AG; CT)și substituții (AT; GC)care au loc în același
timp. Considerăm două modele Markov fixe reprezentate de o matrice de substi-
tuție a nucleotidelor, ce presupune că fiecare nucleotidă se dezvoltă independent de
cealaltă.
Abordarea Jukes-Cantor presupune o perioadă constantă de evoluție, atribuind
o rată la auto-mutația (AA; GG; CC; TT)și altă rată la mutația încrucișată
(Auna din C; G; T ). Matricea Jukes-Cantor de substituție AGCT este:
S=0
BBBBBB@r s s s
s r s s
s s r s
s s s r1
CCCCCCA.
Pentru perioade de timp scurte, perioada evolutivă este constantă: r= 13ϵ
15

șis=ϵ. Pentru perioade mai lungi de timp, rata este reprezentată de o funcție
de timp: r= 0;25(1 + 3 e4t)șis= 0;25(1e4t). Modelul Kimura continuă
luând în considerare faptul că transformările sunt mai frecvente decât substituțiile.
Matricea Kimura de substituție AGCT este:
S=0
BBBBBB@r s u u
s r u u
u u r s
u u s r1
CCCCCCA,
unde s= 0;25(1e4t),u= 0;25(1 + e4te2(+)t)șir= 12su.
3.1 De la distanțe la arbori
În funcție de modelele generatoare Markov și de matricile de substituție cores-
punzătoare (dependente de timp), se va determina matricea distanțelor. Elementele
acestei matrici, dij, reprezintă distanța dintre două secvențe aliniate corect. Putem
să definim matricea distanțelor, (dij), ca o fracție de poziții, f, unde nu se potrivesc
două secvențe, xișixj:dij=3
4log(1 4f=3). Acest model se blochează atunci
când f= 0;75, fapt ce duce la limitarea cantității de nepotrivire dintre cele două
secvențe.
Pentru a folosi, apoi, matricea distanțelor în măsurarea distanțelor actuale dintre
orice pereche de secvențe (adică, pentru construirea unui arbore), considerăm doi
arbori standard:
1.distanțele ultrametrice indică drumuri echidistante de la orice nod frunză la
rădăcină, în timp ce
16

2.distanțele aditive arată că toate perechile de distanțe sunt obținute prin par-
curgerea arborelui.
Arborii ultrametrici nu prea sunt valabili, deoarece distanța ultrametrică presu-
pune o rată uniformă de evoluție, în timp ce distanțele aditive reprezintă un model
mai puțin restrictiv. În practică, matricea distanțelor nu este nici ultrametrică și
nici aditivă.
Atât dualitatea arborilor cât și matricea distanțelor presupun că distanțele sunt
obținute prin parcurgerea arborilor. Dacă folosim distanțe ultrametrice, atunci vom
găsi și arborele corect, minimizând discrepanța dintre distanțele observate și cele
bazate pe arbore. Pe de altă parte, dacă folosim distanțe aditive, vom găsi arborele
corect prin valori apropiate. Ne putem gândi că algoritmul de construire se aseamănă
cu metoda de potrivire a datelor în constrângeri.
3.2 Algoritmi de construire a arborilor
3.2.1 UPGMA
UPGMA (Unweighted Pair Group Method using arithmetic Averages = metoda
neponderată de grupare a perechilor folosind medii aritmetice) este cel mai simplu
exemplu de algoritm de construire a unui arbore. UPGMA conține un algoritm
de clustering ierarhic ce începe de la frunzele arborelui făcându-și drum până la
rădăcină. Ca valoare de intrare, ia o matrice a distanțelor și crează un arbore
ultrametric (adică, în concordanță cu ipoteza moleculară a perioadelor evolutive
egale dintre specii). Numai dacă matricea distanțelor de la intrare este ultrametrică,
atunci algoritmul UPGMA va crea arborele corect. Dacă matricea distanțelor este
aditivă, atunci nu avem nicio garanție că perechile de distanțe ale ramurilor arborilor
17

sunt cele specificate în matricea distanțelor.
În altă ordine de idei, se construiește un arbore, pornind de la grupuri (clus-
tere) 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:
dij=1
jCij
jCjjp2Ci;q2Cjdpq.
Date două clustere CkșiCl, cuCk=Ci[Cj:
dkl=dil
jCij+djl
jCjj
jCij+jCjj.
Algoritmul este următorul:
P1. Se inițializează fiecare secvență cu câte un cluster. Acestea vor forma frunzele
arborelui.
P2. Se găsește perechea de secvențe cu distanța minimă din matricea distanțelor,
D. Această pereche formează primul cluster și desenăm prima parte de arbore
unind perechea. De exemplu, din matricea D, găsim că secvA șisecvB au
distanța minimă de 10. Desenăm arborele unind secvA cusecvB , cu lungimea
de 5. Astfel, distanța totală dintre ele este 10.
P3. Se actualizează matricea D: se adaugă la Do nouă linie și coloană reprezentând
secv AB. Distanța dintre secv ABșisecv Ceste1
2(dAC+dBC). Se înlătură liniile
și coloanele asociate cu secvA șisecvB . În total, matricea se micșorează cu
o linie și o coloană. De aici înainte, uităm complet de secvA șisecvB și
presupunem că avem doar secv AB.
P4. Se repetă pașii P2șiP3până când matricea Ddevine goală.
18

Alți pași ai algoritmului sunt următorii:
Inițializare:
mulțimea clusterelor C=fg
fori= 1::n
Ci=fsecven țaig
C=C[ fCig
definește o frunză ipentru secven țai, plasată la înălțime hi= 0
Iterație:
găsește clusterele Ci,Cjpentru care dije minimă
(în cazul când există mai multe astfel de perechi, se alege una aleator)
construiește Ck=Ci[Cj
for all ClînC
calculează dkl
definește un nod k, părinte pentru ișij,
cuhk=dij=2
C= (C fCi; Cjg)[ fCkg
Terminare:
când rămân doar două clustere CișiCj,
construiește un nod rădăcină la înălțimea hr=dij=2
3.2.2 Neighbor-Joining (unirea valorilor vecine)
Pentru generarea arborilor filogenetici ce reprezintă numărul schimbărilor carac-
terelor prin lungimile ramurilor, acestea fiind proporționale cu perioadele evolutive,
se folosește un algoritm Neighbor-Joining mai complicat. Dacă matricea distan-
țelor de intrare este aditivă, acest algoritm garantează crearea arborelui corect, și
19

poate produce tot un arbore corect, chiar și atunci când matricea distanțelor nu este
aditivă.
Spre deosebire de algoritmul UPGMA, construiește arbori fără rădăcină, și eli-
mină 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 apropiat două secvențe, de data aceasta apropierea fiind
exprimată nu doar în 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):
Dij=dij(ri+rj)
unde
ri=1
jLj2k2Ldik
este utilizat și la reglarea distanței dintre nodurile fiu i,jși părintele k.
Algoritmul este următorul:
P1. Se crează o nouă matrice Mdin matricea distanțelor, D, cu aceleași dimensiuni:
Mij=DijkDik+Djk
N2,
unde Neste numărul secvențelor. Aceasta este metrica ajustată a distanțelor,
ce arată că Mijeste minim dacă și numai dacă ișijsunt vecini.
P2. (similar cu P2din UPGMA): Se găsește perechea de secvențe cu distanța
minimă din noua matrice M. Această pereche formează primul cluster, și
putem desena prima parte din arbore unind valorile din pereche. De exemplu,
din matricea M, găsim secvA șisecvB care au distanța minimă. Unim secvA
20

cusecvB prin noul nod U. Lungimea ramurii de la AlaUse calculează astfel:
DAU=1
2(
DAB+kDAk+DBk
N2)
. De asemenea, DBU=DABDAU.
P3. (similar cu P3din UPGMA): Se actualizează matricea D. Se adaugă la ma-
tricea Do nouă linie și coloană reprezentând nodul U. Distanța dintre Uși
altăsecvC va fi1
2(dAC+dBCdAB). Se șterg liniile și coloanele asociate cu
secvA șisecvB . În total, matricea se micșorează cu o linie și o coloană. De
aici înainte, uităm complet de secvA șisecvB , și presupunem că avem nodul
U.
P4. Se repetă pașii P1,P2șiP3până când matricea Dse golește.
Altfel scris, algoritmul devine:
Inițializare:
mulțimea nodurilor frunză T=mulțimea secvențelor
L=T
Iterație:
alege i,jastfel încât Dijsă fie minim
definește un nou nod k
for all minL
dkm= 1=2(dim+djmdij)
dik= 1=2(dij+rirj)
djk=dijdik
T=T[ fkg,kpărinte pentru ișij
L= (L fi; jg)[ fkg
Terminare:
când rămân doar două noduri ișijînL,
adaugă la Tmuchia dintre ișijde lungime dij
21

3.3 Parsimonia
O altă abordare în crearea arborilor este parsimonia, o metodă ce nu se bazează
pe matricile distanțelor, ci pe alinierea secvențelor. Parsimonia găsește arborele ce
descrie secvențele observate, folosind un număr minim de substituții. Algoritmul
determină două subprobleme computaționale:
1.găsirea costului de parsimonie al unui arbore dat;
2.căutarea prin toate topologiile arborelui.
Prima subproblemă este directă în timp ce cea de-a doua este foarte epuizantă
din punct de vedere al calculatorului și foarte bine descrisă de metodele Monte
Carlo. Din moment ce nu există nicio soluție apropiată și, automat, niciun criteriu
de optimalitate în timpul căutării prin toate topologiile, se poate determina o cău-
tare euristică apropiată. Parsimonia folosește programarea dinamică în procesele de
urmărire și înregistrare pentru a determina nucleotidele ascendente.
3.3.1 Procesul de înregistrare
Algoritmul de înregistrare seamănă cu programarea dinamică pe măsură ce rea-
lizează atribuiri locale la fiecare pas: penalizează nepotrivirile secvențelor, în timp
ce nu atribuie nicio valoare secvențelor potrivite.
•Inițializare: Se setează costul C= 0;k= 2N1
•Iterație:
Dacă keste frunză, atunci setează Rk={
xk[u]}
Dacă knu este frunză, atunci
22

Fiei,jnodurile descendente;
Setează Rk=Ri\Rj, dacă intersecția nu este vidă
Setează Rk=Ri[RjșiC+ = 1 , dacă intersecția este vidă
•Terminație: Costul minim al arborelui pentru coloana uesteC
3.3.2 Procesul de urmărire
Metoda de urmărire pentru găsirea nucleotidelor ascendente implică găsirea unui
drum prin arbore, de la nodurile frunză la o nucleotidă antecedentă (drumul poate
să nu ducă la rădăcina arborelui). Algoritmul poate fi descris sumar, astfel:
•Dacă intersecția a două mulțimi ( AșiB) este vidă, atunci ascendentul este
oriA, oriB, cu cost egal.
•Dacă intersecția a două mulțimi este nevidă, atunci ascendentul este intersec-
ția, cu cost minim.
Această metodă determină un drum neunic, cu o atribuire minimă de substituții,
pentru un arbore dat cu noduri ascunse interne sau intermediare, ce pot corespunde
unor specii dispărute.
3.3.3 Metoda de bootstrap (implementare prin etape succe-
sive)
Un model rapid de creare a arborilor, bazat pe parsimonie, este de construire a
arborilor folosind doar o coloană a matricii multiple de aliniere a secvențelor. Dacă
acest lucru se repetă de mai multe ori și dacă este construită o histogramă a unor
23

anumiți arbori, atunci se poate găsi foarte ușor arborele cel mai convenabil. Avan-
tajul acestei abordări este destul de evident: o complexitate redusă și o acuratețe
foarte bună.
3.4 Parsimonia maximală (filogenetică)
Parsimonia este o metodă statistică fără parametri, folosită adesea în filogenetica
computațională, pentru estimarea filogeniilor. În cadrul parsimoniei, arborele filoge-
netic preferat este arborele ce are nevoie de numai foarte puține schimbări evolutive,
cu scopul de a explica datele observate.
Parsimonia este porțiunea unei clase a metodelor de estimare a arborilor, bazată
pe caractere, metode ce folosesc o matrice de caractere filogenetice discrete pentru a
deduce mai mulți arbori filogenetici optimali pentru o mulțime de genuri, mai precis,
pentru o mulțime de specii sau de populații reproductiv izolate ale unei singure spe-
cii. Funcționalitatea acestor metode este următoarea: evaluează arborii filogenetici
candidați după un criteriu de optimalitate explicit; arborele cu scorul cel mai favo-
rabil va estima cel mai bine legăturile filogenetice ale speciilor incluse. Parsimonia
maximală se folosește împreună cu majoritatea tipurilor de date filogenetice. Până
în zilele de astăzi, a fost singura metodă de estimare a arborilor, folosind caractere,
extrem de folosită pentru datele morfologice.
Estimarea filogeniilor nu este considerată a fi o problemă banală. Există foarte
mulți arbori filogenetici pentru orice mulțime de specii, de dimensiune rezonabilă.
De exemplu, doar zece specii dau peste două milioane de arbori posibili, fără rădă-
cină. Trebuie căutate posibilități de găsire a unui arbore care să corespundă datelor,
folosind criteriul de optimalitate. Totuși, nici datele însele nu duc la vreo soluție
simplă și aritmetică a problemei. Ideal, ne așteptăm ca distribuirea oricăror carac-
24

tere evolutive (cum ar fi trăsăturile fenotipice sau genele allele) să urmeze direct
modelul de ramificație a evoluției. Așadar, putem spune că dacă două organisme
au un caracter comun, atunci ele ar trebui să posede o legătură mai strânsă, față de
un al treilea organism care nu conține acea trăsătură comună, cu condiția ca acel
caracter să nu fi existat la ultimul părinte comun al celor trei organisme. În acest
caz, există o siomorfie simplă. Putem spune că liliecii și maimuțele sunt mult mai
înrudite între ele, față de pești, deoarece maimuțele și liliecii au păr – sinapomorfie.
Totuși, nu putem prezice că maimuțele și liliecii sunt mai bine înrudite între ele, față
de balene, tot pentru că posedă păr, deoarece credem că ultimul lor strămoș comun
avea păr.
Totuși, fenomenele de evoluție convergentă, evoluție paralelă și inversările evo-
luționare (numite mai nou omologii) nu estimează corect filogenia. Din mai multe
motive, se poate ca două organisme să posede o caracteristică ce nu a fost prezentă
la antecedentul lor comun. Dacă foloseam această caracteristică pentru a evidenția
relațiile, am fi construit un arbore greșit. Datele reale filogenetice cuprind omologii
substanțiale, părțile diferite ale acestor date indicând câteodată legături foarte dis-
tincte. Metodele folosite pentru crearea arborilor filogenetici rezolvă contradicțiile
din cadrul datelor, alegând arborele filogenetic cel mai adecvat pentru majoritatea
datelor, restul de date nepotrivite neluându-se în calcul. De obicei, se crede că par-
simonia presupune raritatea convergenței; de fapt, chiar și trăsăturile rezultate în
mod convergent au câteva valori în analizele filogenetice bazate pe parsimonia ma-
ximală, extinderea convergenței neafectând în mod sistematic rezultatele metodelor
parsimoniei.
25

3.4.1 Datele de tip caracter
Datele de intrare folosite în cadrul analizei parsimoniei maximale sunt în formă
de “caractere” pentru o varietate de specii. Nu există o definiție generalizată pentru
caracterul filogenetic, însă, în mod operațional, un caracter reprezintă un atribut,
sau este o axă de-a lungul variației speciilor. Aceste atribute pot fi fizice (mor-
fologice), moleculare, genetice, fiziologice sau comportamentale. Regula pe care o
urmează caracterele este faptul că variația folosită pentru analiza lor este una ere-
ditară. Chiar dacă variația este direct ereditară sau indirect ereditară (de exemplu,
comportamente învățate), problema nu este rezolvată pe de-a-ntregul.
Fiecare caracter este împărțit în stări de caracter discrete, în care sunt clasificate
variațiile observate. Stările de caracter mai sunt numite și descriptori ce descriu
condiția substratului de caracter. De exemplu, caracterul “culoarea ochilor” poate
avea stările de “albastru” și “maro”. Caracterele pot avea două sau mai multe stări
(ele pot avea și o singură stare, dar nu duc la parsimonie maximală, și deci, se
exclud).
Caracterele de codificare pentru analiza filogenetică nu reprezintă o știință exactă,
existând numeroase probleme. În mod tipic, speciilor care se aseamănă între ele
dintr-un anumit atribut, li se dă aceeași stare, față de cele cu stări diferite. Atunci
când nu sunt stabilite stările de caracter, sau când nu cuprind toate variațiile po-
sibile, cazul nu este deloc simplu. Cum se marchează caracterul “culoarea ochilor”
pentru o specie sau un individ cu ochi căprui sau verzi? Așa cum am menționat mai
sus, codificarea caracterelor se bazează, în general, pe similaritate: ochii căprui și
verzi pot fi considerați cu albastru, pentru că se aseamănă mai mult cu această cu-
loare (deschisă), caracterul putând fi recodificat astfel: “culoarea ochilor: deschisă;
închisă”. Mai mult, există și caractere cu mai multe stări, precum “culoarea ochilor:
maro; căprui, albastru; verde”.
26

Ambiguitățile din conturarea și marcarea stărilor de caracter pot fi confuze,
discutabile, dar și greșite în analiza filogenetică a datelor de tip caracter. Observăm
că, în exemplul de mai înainte, “ochi: prezenți; absenți” reprezintă un caracter
posibil ce duce la o discuție, deoarece caracterul “culoarea ochilor” nu se aplică dacă
ochii nu sunt prezenți. Pentru astfel de situații, se marchează cu “?” (necunoscut),
deși ori “X”, ori “-” (ultimul folosit la datele de tip secvență) se folosesc pentru
a distinge cazurile în care un caracter cu stări necunoscute nu poate fi marcat.
Implementările actuale în parsimonia maximală tratează valorile necunoscute prin
aceeași manieră: motivele pentru care datele nu sunt cunoscute nu afectează deloc
procesul de analizare. Programul tratează cazul “?” ca și cum ar implica cei mai
puțini pași în plus în arbore, deși nu reprezintă o parte explicită a algoritmului.
Datele genetice sunt verificate de metodele filogenetice bazate pe caractere, pre-
cum parsimonia maximală, deoarece secvențele de proteine și de nucleotide sunt
discrete. O anumită poziție dintr-o secvență de nucleotide poate fi adenină, cito-
zină, guanină, timină sau uracil, sau un spațiu gol; o poziție (o clasă de resturi)
dintr-o secvență de proteine va fi unul din aminoacizii bazici sau din spațiile goale.
Așadar, marcarea caracterelor nu prea este ambiguă, numai în cazurile în care me-
todele de secvențiere nu mai produc o atribuire definitivă unei anumite poziții din
secvență. Spațiile goale din secvențe mai sunt luate ca și caractere, deși nu prea are
sens cum să se codifice.
Caracterele mai pot fi ordonate sau neordonate. Însă acest lucru nu este impor-
tant pentru cele binare (cu două stări). Pentru cele cu mai multe stări, caracterele
neordonate sunt considerate având un “cost” egal (sau un număr egal de “evenimente
evolutive”), pentru a trece dintr-o stare într-alta; mai mult, nu este necesar să se
treacă prin toate stările intermediare. Caracterele ordonate conțin o secvență parti-
culară în care stările trebuie să se întâmple în timpul evoluției, astfel încât trecerea
27

prin câteva stări să necesite minim o stare intermediară. Acest lucru se mai poate
interpreta ca trecerea prin perechi de stări diferite să aibă costuri diferite. În exem-
plul caracterului “culoarea ochilor”, se pot lăsa caracterele neordonate, ceea ce va
duce la același “cost” evolutiv pentru maro-albastru, verde-albastru, verde-căprui,
etc. Altfel, caracterele pot fi ordonate maro-căprui-verde-albastru; acest lucru în-
seamnă că există două evenimente evolutive de la maro la verde, trei evenimente
evolutive de la maro la albastru și unul de la maro la căprui. Iarăși, se mai poate
interpreta ca având nevoie de ochi pentru a evolua printr-un “stadiu de căprui” pen-
tru a ajunge de la maro la verde, printr-un “stadiu de verde” pentru a ajunge de la
căprui la albastru, etc.
Există multe discuții despre utilitatea și oportunitatea ordonării caracterelor, dar
niciun consens. Caracterele se ordonează atunci când există o tranziție logică, onto-
genetică sau evolutivă între stări, de exemplu, “picioare: scurte; medii; lungi”. Sunt
acceptate doar unele din aceste criterii. Există o analiză neordonată cu caractere
ordonate ce arată o tranziție ordonată corect la arborele rezultat (un raționament
circular). Caracterele pot rămâne total neordonate, necesitând o analiză pentru a
deduce tranzițiile evolutive ce urmăresc o anumită tendință.
Mai există posibilitatea aplicării ponderării diferențiale caracterelor individuale.
Asta înseamnă că se asociază un “cost” de 1. Astfel, unele caractere pot indica
adevăratele legături evolutive dintre specii și astfel, ele sunt ponderate la o valoare
de 2 sau mai mare. Schimbările din aceste caractere vor fi calculate ca doi “pași”
evolutivi și nu ca unul, atunci când se calculează marcările arborelui. În trecut, au
fost multe dezbateri legate de ponderarea caracterelor. Toate caracterele sunt acum
ponderate în mod egal, deși mai există și excepții. De exemplu, datele de frecvență
ale genelor allele sunt grupate și marcate ca niște caractere ordonate. În aceste
cazuri, caracterul însuși este subponderat, astfel încât să fie mai puține schimbări
28

minore în frecvența genelor allele, decât schimbările majore din alte caractere. De
asemenea, a treia poziție de codon dintr-o secvență de nucleotide de codificare este
în mod particular instabilă, fapt ce o subponderează, sau i se dă ponderea 0, în-
semnând că nu aparține omologiei. În unele cazuri, se repetă analizările, în care
caracterele sunt reponderate invers față de gradul omologiei din analiza precedentă
(se mai numesc ponderări succesive). Această tehnică poate fi interpretată tot ca
un raționament circular.
Schimbările stărilor de caracter pot fi ponderate fiecare în parte. Acest lucru se
întâmplă la datele de secvențiere a nucleotidelor; s-a determinat, în mod empiric, că
anumite schimbări de bază ( AC,AT,GC,GT, dar și invers) se întâmplă
mai rar decât altele, aceste schimbări fiind ponderate mai mult. Ca și în ordonarea
caracterelor, caracterele ordonate sunt înțelese ca o formă de ponderare a stărilor
de caractere.
Unii sistematicieni preferă să excludă caracterele cunoscute ca omologii, sau ce
conțin foarte multe intrări necunoscute (“?”). Studiul teoretic și de modelare a
demonstrat că excluderea acestor caractere strică acuratețea decât să o îmbunătă-
țească. Același lucru se întâmplă și cu caracterele variabile din speciile terminale:
studiile teoretice, de congruență și de modelare au demonstrat că astfel de caractere
polimorfice conțin informații filogenetice semnificative.
3.4.2 Procesul de selecție a speciilor
Timpul necesar pentru o analizare a parsimoniei (sau pentru orice analiză filo-
genetică) este proporțional cu numărul speciilor (și caracterelor) incluse în analiză.
Deoarece mai multe specii necesită ca mai multe ramuri să fie estimate, apare și mai
multă nesiguranță în analizele mari. Deoarece costurile de timp și de colectare a
datelor sunt la fel de mari ca și numărul de specii incluse, majoritatea analizelor lu-
29

crează cu numai o parte din speciile care pot fi selectate. Și este normal că s-a ajuns
la faptul că sunt necesare patru specii (numărul minim necesar pentru a crea un
arbore semnificativ fără rădăcină) pentru o analiză filogenetică adecvată, și că mai
multe caractere sunt mai importante decât un număr mare de specii în filogenetică.
Acest lucru a condus la o controversă dură referitoare la selecția speciilor.
Studiile empirice, teoretice și de simulare au dus la demonstrații dramatice referi-
toare la importanța selecției adecvate ale speciilor. Majoritatea demonstrațiilor pot
fi rezumate printr-o simplă observare: o matrice de date filogenetice are dimensiu-
nile speciilor de caractere măsurate în timp. Dublarea numărului de specii dublează
cantitatea de informații dintr-o matrice, la fel de exact ca și dublarea numărului
de caractere. Fiecare specie reprezintă un nou model pentru fiecare caracter, dar,
mai important, reprezintă o nouă combinație de stări de caracter. Pe lângă faptul
că determină locul unei anumite specii în arbore, stările de caracter mai afișează și
întreaga analiză, în care legăturile diferite dintre speciile rămase sunt favorizate prin
estimările schimbărilor de caracter.
Cel mai mare defect din analiza parsimoniei, acela de ramură lungă, este evi-
dențiat de selecția slabă a speciilor, mai ales în cazul cu patru specii. Acesta este
destul de bine înțeles, deoarece selecția adițională a caracterelor nu îmbunătățește
calitatea estimării. Pe măsură ce se adaugă specii, ramurile lungi se rup (în special,
în cazul fosilelor), îmbunătățindu-se efectiv estimarea schimbărilor stărilor de carac-
ter. Datorită informației abundente adăugată de selecția speciilor, este posibil să se
producă estimări de mare acuratețe a filogeniilor, cu sute de specii folosind numai
câteva mii de caractere.
Deși s-au studiat foarte multe cazuri, încă mai este de lucru la strategiile de
selectare a speciilor. Datorită avantajelor performanțelor calculatoarelor, a costului
redus și a automatizării crescute a secvențierii moleculare, dimensiunile procesului
30

de selectare cresc continuu și studiile referitoare la legăturile dintre sutele de specii
(sau a altor entități terminale, ca genele) devin extrem de comune. Și caracterele
adiționale sunt folositoare, numărul acestora crescând mereu.
Unii clasificatori preferă să excludă speciile bazate pe numărul intrărilor de carac-
tere necunoscute (“?”), sau care tind “să sară în jurul arborelui” în timpul analizelor
(adică, sunt “jokeri”). Așa cum este scris în continuare, simularea și munca teoretică
au demonstrat că excluderea speciilor strică acuratețea analizei decât să o îmbu-
nătățească. Deși aceste specii pot genera mai mulți arbori parsimoniali, metodele
de subarbori de convenție și de consens redus încă pot extrage informații pe baza
legăturilor convenabile.
S-a observat că incluziunea mai multor specii tinde să scadă valorile de suport
generale (prin procentajele instrucțiunilor inițiale sau prin indecșii de scădere). Ca-
uza este următoarea: pe măsură ce speciile adiționale sunt adăugate la arbore, ele
subdivid ramurile pe care sunt atașate, și astfel, dizolvă informația de pe ramură. În
timp ce suportul ramurilor individuale se reduce, cel al legăturilor totale crește. Să
considerăm analiza ce produce următorul arbore: (pește, (șopârlă, (balenă, (pisică,
maimuță)))). Adăugarea unui șobolan și a unei morse va reduce suportul pentru
grupul (balenă, (pisică, maimuță)), din cauză că șobolanul și morsa pot să fie sau nu
în cadrul acestui grup, și din moment ce aceste cinci animale sunt toate înrudite între
ele, ar trebui să existe incertitudine în legăturile lor. În cadrul erorii, este imposibil
să determinăm orice legătură a acestor animale, unele cu altele. Totuși, șobolanul și
morsa vor adăuga date de tip caracter ce vor consolida gruparea a câte două animale
din cele cinci, mai puțin peștele și șopârla; unde analiza inițială devine greșită, de
exemplu, prin prezența cozii la pește și la balenă, prezența morsei cu același zgomot
și cu aceeași coadă ca a balenei, dar cu mustăți ca pisica și șobolanul, leagă ferm
balena de mamifere.
31

Pentru a rezolva această problemă, subarborii de convenție, consensul redus și
analiza cu dubla scădere încearcă să identifice relațiile suportate (în formă de “in-
strucțiuni cu n specii”, cum este instrucțiunea cu patru specii, “(pește, (șopârlă,
(pisică, balenă)))”), decât arborii întregi. Dacă scopul unei analize este de a rezulta
într-un arbore corect, ca în cazul filogeneticii comparative, atunci aceste metode nu
pot rezolva problema. Totuși, dacă estimarea arborelui nu prea se confirmă, atunci
rezultatele oricărei analize a acelui arbore vor fi prea suspecte pentru a fi utilizate.
3.4.3 Analiza
O analiză a prsimoniei maximale se rezolvă printr-o metodă foarte simplă. Ar-
borii sunt marcați în funcție de gradul în care ei duc la o distribuire parsimonială a
datelor de tip caracter. Cel mai parsimonial arbore din mulțimea de date reprezintă
ipoteza preferată a legăturilor dintre speciile analizate.
Arborii sunt marcați (evaluați) folosind un algoritm simplu de determinare a
numărului de “pași” (tranziții evolutive) necesari pentru explicarea distribuirii fie-
cărui caracter. În esență, un pas reprezintă o schimbare de la o stare de caracter
la alta, deși la caracterele ordonate, pentru unele tranziții sunt necesari mai mulți
pași. Contrar gândirilor tradiționale, algoritmul nu atribuie, în mod explicit, stări
particulare de caracter la nodurile arborelui (intersecțiile ramurilor): cel mai mic
număr de pași poate duce la atribuiri și distribuiri multiple și de costuri egale, ale
tranzițiilor evolutive. Însă, se optimizează numărul total de schimbări.
Pentru minim opt specii, există mult mai mulți arbori filogenetici posibili căutați
în mod complet. Pentru căutarea printre acești arbori posibili, se folosesc mai mulți
algoritmi. Majoritatea algoritmilor presupun luarea unui arbore inițial (de obicei,
se ia arborele preferat de la ultima iterație a algoritmului) și perturbarea acestuia
pentru a vedea dacă schimbarea produce înregistrări mai mari.
32

Arborii rezultați din căutarea pe baza parsimoniei nu au rădăcină. Ei arată toate
relațiile posibile ale speciilor incluse, dar nu conțin nicio formulare a timpilor relativi
de divergență. Se alege o anumită ramură ca rădăcină a arborelui. Această ramură
este considerată ca nefăcând parte din celelalte ramuri, ce împreună formează un
grup monofiletic. Acest lucru oferă o parte relativă de timp arborelui. O alegere
incorectă a rădăcinii poate duce la legături incorecte în arbore, chiar dacă acesta
este unul corect, fără rădăcină.
Analiza parsimoniei duce, de obicei, la un număr de cei mai parsimoniali ar-
bori egali (MPT). Foarte mulți arbori MPT sunt considerați a fi un eșec analitic,
crezându-se că au o legătură cu valorile de intrare absente (“?”) din mulțimea de date,
caracterele arătând prea multă omologie, sau arătând prezența speciilor topologic
labile de “jokeri” (ce pot avea multe intrări vide). Au fost propuse multe metode de
reducere a numărului de arbori MPT, incluzând ștergerea caracterelor sau a speciilor
cu mari cantități de date lipsă înainte de procesul de analizare, ștergerea sau sub-
ponderarea caracterelor foarte asemănătoare (ponderare succesivă), sau înlăturarea
speciilor cu caracter “joker” (metoda filogenetică de trunchiere) a posteriori și apoi,
reanalizând datele.
Numeroase simulări și studii teoretice au demonstrat că speciile și caracterele cu
foarte multe date lipsă, caracterele foarte asemănătoare și speciile cu caracter “joker”
contribuie la analiză. Deși excluderea caracterelor sau a speciilor poate apărea
ca îmbunătățind soluția, arborele rezultat folosește mai puține date, fiind astfel o
apreciere mai puțin de încredere a filogeniei (numai dacă speciile sau caracterele nu
sunt informaționale). Consensul actual general este că folosirea mai multor arbori
MPT reprezintă un rezultat analitic valabil; se arată că nu sunt suficiente date
pentru a rezolva complet arborele. În multe cazuri, arborii MPT au o structură
comună substanțială, diferențele fiind mici și ducând la incertitudini referitoare la
33

plasarea a câtorva specii. Există câteva metode de rezumare a legăturilor din cadrul
acestei mulțimi, incluzând arborii de consens ce indică legături comune printre toate
speciile și incluzând arbori convenționali simplificatori, ce arată o structură comună
după simplificarea temporară a speciilor de tip “joker” de la fiecare arbore, până
corespund toți. Consensul redus mai conține un pas în plus, afișând toți subarborii
(automat și toate legăturile) susținuți de cei de la intrare.
Chiar dacă se returnează mulți arbori MPT, analiza parsimoniei produce, esen-
țialmente, orice fel de interval de apreciere și de neîncredere într-un singur punct.
Acest lucru a trecut la nivelul criticii, din moment ce mai mult ca sigur există erori
în estimarea arborelui cel mai parsimonial, și din cauză că metoda nu conține mij-
loace de stabilire a cât de sensibile sunt rezultatele ei la această eroare. Se folosesc
mai multe metode de evaluare a suportului.
Bine-cunoscutele proceduri statistice de re-eșantionare, tehnica bootstrap (im-
plementare prin etape succesive) și tehnica jackknife, au fost utilizate în analiza
parsimoniei. Tehnica jackknife, ce implică re-eșantionarea fără înlocuire (“lasă-unul-
afară”) se poate folosi pe caractere sau pe specii; interpretarea se poate complica
în cazul speciilor, deoarece variabila de interes este arborele, iar comparația dintre
arborii cu specii diferite nu este deloc simplă. Tehnica bootstrap, ce implică re-
eșantionarea cu înlocuire (mostra x bifează aleator mostrele de dimensiune x, acești
itemi putând fi aleși de mai multe ori), se folosește numai pe caractere, pentru că
adăugarea speciilor duplicate nu schimbă rezultatul analizei parsimoniei. Tehnica
bootstrap este mult mai des folosită în filogenetică (față de alte domenii); ambele
metode implică un număr aleator mare de iterații repetate ce includ perturbările
datelor originale urmate de analiză. Sunt extrași arborii MPT rezultați din fiecare
analiză, iar rezultatele se prezintă pe un arbore de consens cu 50% reguli majoritare,
având ramurile (nodurile) etichetate cu procentajul bootstrap al arborilor MPT din
34

care apar. “Procentajul bootstrap” (ce nu este o valoare P) se folosește ca o măsură
de suport. În mod tehnic, se presupune că este o măsură de repetabilitate, probabili-
tatea că ramura respectivă (nod sau grup) s-ar recupera, dacă speciile s-ar eșantiona
din nou. Testele experimentale cu filogenii virale confirmă că procentajul bootstrap
nu estimează corect procesul de repetabilitate din filogenetică, dar este un estimator
rezonabil în cazul acurateții. De fapt, s-a arătat că procentajul bootstrap, cu rol de
estimator al acurateții, este greșit, aceste rezultate subevaluând încrederea (astfel
încât pentru un suport de 70%, încrederea devine 95%). Totuși, în anumite cazuri,
nu se pot stabili direcțiile erorilor, tehnica bootstrap cu valori înalte îndicând că și
încrederea mult prea mare nu este întemeiată.
O altă metodă de evaluare a suportului este suportul Bremer, sau indexul de
scădere (ce nu este, practic, un index). Acesta este diferența calculată într-un nu-
măr de pași dintre punctajele arborilor MPT și punctajele arborilor MPT care nu
conțin un anumit grup (nod, ramură). Indexul de scădere mai poate fi numărul
de pași adăugați pentru a înlătura grupul respectiv; indexul de scădere arată cât
de mare trebuie să fie eroarea estimării punctajului arborelui MPT, ca să nu mai
poată fi susținută în analiză, deși nu este necesar acest lucru. Valorile indexului de
scădere sunt, de obicei, foarte scăzute (de unul sau doi pași), însă sunt proporțio-
nale cu procentajele bootstrap. Totuși, interpretarea acestor valori este greoaie, ele
fiind preferate de autorii cu păreri filosofice legate de tehnica bootstrap, deși mulți
sistematicieni de morfologie, mai ales paleontologii, preferă ambele tehnici. Analiza
cu dublă scădere este echivalentă cu consensul redus ce evaluează indexul de scă-
dere pentru toate relațiile posibile ale subarborilor dintr-un arbore (instrucțiuni cu
n specii).
35

3.4.4 Probleme în estimarea filogeniei parsimoniei maximale
Cea mai simplă abordare este parsimonia maximală, care totuși, nu este solidă
din punct de vedere statistic. Asta înseamnă că și dacă i se dau date suficiente,
nu garantează crearea arborelui corect de probabilitate mare. Consistența, în acest
caz fiind convergența monotonă a răspunsului corect cu adăugarea a mai multor
date, reprezintă o proprietate oportună pentru orice metodă statistică. Așa cum
a fost demonstrată în 1978 de către Joe Felsenstein, parsimonia maximală poate
fi insuficientă în anumite condiții. Aceste condiții se întâmplă în situații numite
“atracția ramurilor lungi”, în care există două ramuri lungi (un număr mare de
substituiri) pentru două caractere ( AșiC), și două ramuri scurte pentru alte două
caractere ( BșiD).AșiBdiverg dintr-un antecedent comun, ca și CcuD.
Să presupunem, cât mai simplu, un singur caracter binar (poate fi + sau -). Din
cauză că distanța dintre BșiDeste mică, mai în toate cazurile, BșiDse vor
asemăna. În acest caz, vom presupune că BșiDsunt cu +(+șisunt aleator
distribuite și inversarea lor face parte din definiție). Dacă suntem în acest caz, există
patru posibilități rămase. AșiCsunt amândouă cu +, asta însemnând că toate
speciile sunt la fel și că toți arborii au aceeași lungime. Apoate fi +șiCeste,
situație în care doar un singur caracter este diferit, arborii având aceeași lungime.
Analog, AesteșiCeste +. Singura posibilitate rămasă este ca AșiCsă fie . În
acest caz, grupăm pe AcuCși pe BcuD. Ca rezultat, pentru un arbore de acest
tip, cu cât colectăm mai multe date (adică, cu cât studiem mai multe caractere), cu
atât ne îndreptăm spre arborele greșit.
O metodă simplă și efectivă de determinare dacă “atracția ramurilor lungi” afec-
tează sau nu topologia arborelui, este metoda SAW, numită după Siddal și Whiting.
Dacă într-o pereche de specii ( AșiB) se suspectează a fi ramuri lungi, atunci se
înlătură specia A(“se taie” ramura) și se analizează din nou. Apoi, se înlătură A
36

și se înlocuiește B, reanalizându-se din nou. Dacă una din cele două specii apare
în puncte diferite ale ramurii în absența celeilalte, atunci este prezentă “atracția
ramurii lungi”. Din moment ce ramurile lungi nu se pot atrage între ele, atunci când
se analizează una din ele, plasarea stabilă a speciilor între analizări arată că nu este
nicio problemă cu ramurile lungi.
Mai sunt valabile și alte metode de estimare a filogeniei: probabilitatea maxi-
mală, inferența filogenetică bayesiană, neighbor-joining (unirea valorilor vecine) și
metodele cvartete. Primele două folosesc o funcție de probabilitate, care dacă este
utilizată corect, nu ia în considerare ramurile lungi. Aceste modele sunt parametrice,
însemnând că se bazează pe un model explicit de evoluție a caracterelor. Însă, s-a
arătat că, pentru unele modele suboptimale, aceste metode pot fi și incompatibile.
Parsimonia maximală poate fi complicată în cazul în care găsirea celui mai par-
simonial arbore reprezintă o problemă NP grea. Fiind dată aleator o mulțime mare
de specii, singura modalitate disponibilă și eficientă de găsire a unei soluții este folo-
sirea metodelor euristice ce nu garantează recuperarea celui mai parsimonial arbore.
Aceste metode folosesc algoritmi hill-climbing (găsirea maximului) pentru a ajunge
progresiv la arborele cel mai bun. Totuși, s-a mai arătat că există “insule de arbori”
ale soluțiilor optime, analiza blocându-se în aceste cazuri. Așadar, sunt necesare
metode euristice complexe și flexibile pentru a se asigura că s-a explorat în mod
adecvat întregul spațiu al arborelui. Sunt disponibile mai multe metode euristice:
interschimbarea celei mai apropiate valori vecine (NNI), divizarea/reîmbinarea ar-
borelui (TBR) și cuplarea filogenetică. Clar, această problemă nu este unică pentru
MP; orice metodă ce folosește un criteriu optimal se confruntă cu aceeași problemă,
și nici una nu se rezolvă ușor.
37

3.4.5 Critici
S-a remarcat că o problemă majoră, mai ales în domeniul paleontologiei, este
aceea că parsimonia maximală presupune că singurul mod ca două specii să aibă
aceeași nucleotidă pe aceeași poziție, este ca acestea să fie înrudite genetic. Acest
lucru afirmă că aplicațiile filogenetice din parsimonie presupun ca toată similaritatea
să fie omoloagă (alte interpretări, de genul că două organisme pot să nu fie deloc
înrudite, nu au niciun sens). Însă, aici, nu este cazul: ca și orice altă formă de
estimare a filogeniei bazată pe caractere, parsimonia se folosește pentru a testa
natura omoloagă a similitudinilor, prin găsirea arborelui filogenetic ce explică toate
asemănările.
De exemplu, păsările și liliecii au aripi, în timp ce crocodilii și oamenii nu au
aripi. Dacă acestea sunt singurele date disponibile, atunci parsimonia maximală
tinde să grupeze crocodilii cu oamenii, și păsările cu liliecii, la fel ca orice altă
metodă de inferență filogenetică. Credem că, de fapt, oamenii sunt mai apropiați
de lilicei, decât față de crocodili sau de păsări. Această convingere este fondată
pe alte date ce nu s-au luat în considerare în acest exemplu cu un singur caracter
(aripile). Dacă s-ar mai adăuga în analiză și o mică fracțiune de alte date, cum ar
fi, informații despre structura scheletică, morfologia țesutului moale, tegumentul,
comportamentul, genetica, etc, semnalul filogenetic slab produs de prezența aripilor
la păsări și lilieci ar fi copleșit numeric de multitudinea de date susținând arborele
(om, liliac)(pasăre, crocodil).
Se tot spune, de obicei, că parsimonia este irelevantă inferenței filogenetice, deo-
arece “evoluția nu este parsimonială”. În majoritatea cazurilor, nu se propune nicio
alternativă explicită; astfel, se va prefera orice metodă statistică. Mai mult, nu s-
ar înțelege nimic dacă propoziția “evoluția este parsimonială” ar fi fost adevărată.
Cumva, s-ar înțelege că de-a lungul istoriei, au existat mai multe schimbări de ca-
38

ractere decât cele prezise de criteriul parsimoniei. Acest lucru ar fi posibil dacă
estimarea filogeniei din parsimonie ar reconstrui numărul minim de schimbări ne-
cesare pentru a descrie arborele. Totuși, de-a lungul studiilor simulatoare, tesând
filogeniile virale in vitro și congruența cu alte metode, s-a arătat că acuratețea par-
simoniei nu este compromisă mai deloc. Analiza în parsimonie folosește numărul
schimbărilor de caracter pe arbori pentru a alege arborele cel mai bun, însă nu ne-
cesită chiar așa de multe schimbări. Pe măsură ce schimbările nejustificate sunt
distribuite aleator prin arbore (o așteptare rezonabilă vidă), rezultatul nu ar tre-
bui să fie greșit. În practică, această tehnică este complexă: parsimonia maximală
înlătură erorile minime rezultate din alegerea arborelui cu cele mai puține schimbări.
Se poate schița o analogie alegând contractanții ce își estimează, inițial, costul
slujbei lor. Costul actual final s-ar putea să fie mult mai mare decât cel estimat. Lă-
sând la o parte acest lucru, alegerea contractantului ce a dat cea mai mică apreciere,
ar trebui teoretic să rezulte în cel mai mic cost final de proiect. Se întâmplă acest
lucru, deoarece în absența altor date, am presupune că toți contractanții impor-
tanți au același risc de depășire a costurilor. Desigur că, în practică, alegerile lipsite
de scrupule pot deforma rezultatul; și în filogenetică, unele probleme (de exemplu,
atracția ramurii lungi) pot afecta rezultatele. Totuși, în ambele cazuri, nu se poate
spune dacă rezultatul va fi eronat sau nu, sau gradul acestuia de eroare. Și în cazul
parsimoniei, nu se poate spune dacă datele sunt derutante sau nu, fără a se compara
cu alte date.
În cadrul parsimoniei, se afirmă că schimbarea evolutivă este rară și că omologie
(convergența și inversarea) este minimă în cadrul evoluției. Acest lucru nu este
total adevărat: parsimonia minimizează numărul convergențelor și inversărilor date
de arborele preferat, însă acest fapt duce la foarte multe evenimente asemănătoare.
Este mai corect faptul că parsimonia admite doar o cantitate minimă de schimbări
39

rezultate din date. Asta nu înseamnă că acestea sunt singurele schimbări petrecute;
pur și simplu, nu există schimbări pentru care nu sunt date. Spus și mai scurt,
avem că “parsimonia minimizează omologiile admise, dar nu admite că omologia
este minimală”.
Câteodată, parsimonia mai este asociată cu noțiunea că “cea mai simplă explica-
ție posibilă este și cea mai bună”. Parsimonia preferă soluția ce necesită cel mai mic
număr de presupuneri neîntemeiate și de concluzii intolerabile, soluția cu cea mai
mică distanță teoretică dintre date. Aceasta este o abordare banală în știință, atunci
când ne confruntăm cu sisteme foarte complexe ce sfidează modelele simple. Prin
nicio metodă, parsimonia nu oferă o presupunere “simplă”. Ca o regulă generală,
majoritatea mulțimilor de date de tip caracter sunt așa de “zgomotoase”, încât nicio
soluție cu adevărat “simplă” nu este posibilă.
3.4.6 Metode alternative
Există multe alte metode de înțelegere a filogeniilor bazate pe date de tip caracter
discrete. Fiecare dintre acestea oferă atât avantaje cât și dezavantaje. Majoritatea
metodelor au și partizani, dar și denigratori; în mod special, parsimonia s-a menținut
superioară din punct de vedere filosofic.
Probabilitatea maximală
Printre cele mai populare metode filogenetice alternative, este și inferența filo-
genetică a probabilității maximale, mai numită și “probabilitate” sau “ML”. Proba-
bilitatea maximală reprezintă un criteriu optimal, la fel ca și parsimonia. În mod
automat, analiza probabilității maximale funcționează la fel ca și analiza parsimo-
niei, în care arborii sunt marcați în funcție de caractere, fiind selectat arborele cu
cel mai mare punctaj. Probabilitatea maximală este o metodă statistică și parame-
40

trică, ce folosește un model explicit de evoluție a caracterelor. Astfel de metode sunt
mult mai puternice decât cele statistice fără parametrii, ca parsimonia, numai dacă
modelul folosit este o aproximație logică a proceselor ce produc datele. Se pare că
probabilitatea maximală a depășit parsimonia prin datele secvență a nucleotidelor,
iar inferența filogenetică bayesiană, ce folosește funcția de probabilitate, devine din
ce în ce mai răspândită.
Probabilitatea este copia relativă a probabilității absolute. Dacă știm numărul de
ieșiri posibile ale unui test ( N), și cunoaștem numărul acelor ieșiri care se potrivesc
unui criteriu particular ( n), atunci putem spune că probabilitatea criteriului după
care se execută testul este n=N. Astfel, probabilitatea de a ieși cap prin aruncarea
unei monezi este 50% (1/2). Dacă nu cunoaștem numărul de ieșiri posibile, nu vom
putea calcula probabilitățile. Totuși, dacă observăm că un rezultat apare de două ori
mai des decât alt rezultat după un număr mare aleator de teste, putem spune că acel
rezultat are o probabilitate de două ori mai mare. Probabilitățile sunt proporționale
cu cele adevărate: dacă o valoare de ieșire are o probabilitate de două ori mai mare,
putem spune că este de două ori mai probabilă, deși nu putem ști cât de probabilă
este.
Practic, probabilitatea unui arbore nu poate fi calculată în mod direct. Probabi-
litatea datelor ce construiesc un arbore poate fi calculată, dacă se admite o mulțime
de probabilități specifică a schimbărilor de caracter (un model). Partea critică a ana-
lizei probabilităților este că probabilitatea datelor ce formează arborele este egală
cu probabilitatea arborelui ce oferă datele. Astfel, arborele cel mai convenabil este
cel cu cea mai mare probabilitate de construire a datelor observate.
Probabilitatea maximală, așa cum este implementată în filogenetică, folosește un
model stohastic ce dă posibilitatea schimbării unui anumit caracter în orice punct
din arbore. Acest model poate lucra cu un număr mare de parametri ce justifică di-
41

ferențele din probabilitățile stărilor specifice, ce explică probabilitățile unor anumite
schimbări și diferențele dintre probabilitățile schimbărilor între caractere.
Un arbore de probabilitate conține ramuri ale căror lungimi sunt semnificative
(adică este o filogramă); aceste lungimi sunt, de obicei, proporționale cu probabi-
litatea medie de schimbare a caracterelor pe acea ramură. Astfel, pe o ramură de
lungime 1, ne așteptăm la o medie de o schimbare pe caracter, ceea ce este mult.
Starea fiecărui caracter se desenează pe arbore, iar probabilitatea distribuirii stărilor
caracterului se calculează folosind modelul și lungimile ramurilor, ce pot fi modifi-
cate pentru a mări probabilitatea datelor. Aceasta este probabilitatea unui anumit
caracter dintr-un arbore. Probabilitățile tuturor caracterelor se înmulțesc; ele sunt
transformate negativ în logaritmi și apoi însumate (rezultând același efect), dato-
rită numerelor ce scad foarte repede. Această sursă reprezintă probabilitatea datelor
sau probabilitatea arborelui. Ne convine arborele cu cea mai mare probabilitate (cea
mai mică probabilitate negativă transformată în logaritm). În analogia referitoare
la alegerea unui contractant, probabilitatea maximală se va asemăna foarte mult
cu procesul de strângere a datelor, la costul final a tuturor slujbelor omparabile
realizate de fiecare contractant de-a lungul unui an, și cu procesul de selectare a
contractantului cu cel mai mic cost mediu. Această metodă depinde foarte mult
de compararea slujbelor, dar dacă acestea sunt alese corect, se va estima mult mai
bine costul actual al unei slujbe. Mai mult, metoda nu va conține erori în estimarea
contractantului, deoarece se bazează pe costul final și nu pe estimări (care pot fi
eronate).
În practică, probabilitatea maximală tinde să favorizeze arborii care se aseamănă
foarte mult cu cei mai parsimoniali din aceeași mulțime de date. În anumite situații
în care arborii MPT sunt eronați, incluzând și “atracția ramurilor lungi”, trebuie să
se depășească parsimonia. Să luăm aminte că performanțele probabilității depind
42

de calitatea modelului folosit; un model incorect poate duce la un rezultat eronat.
Studiile au arătat că incluziunea unui parametru ce justifică diferențele perioadelor
de evoluție a caracterelor, poate fi decisivă în estimarea adecvată a filogeniilor; eșecul
modelării filogeniilor sau a altor parametrii decisivi duce la rezultate incorecte sau
eronate. Parametrii model sunt, de obicei, evaluați din mulțimi de date, iar numărul
și tipul acestora se determină folosind raportul ierarhic al lui D’Alembert de pro-
babilitate. Se va începe descrierea amănunțită a consecințelor modelelor specificate
greșit.
Probabilitatea este, în general, văzută ca o metodă mult mai convenabilă decât
parsimonia, fiind o metodă statistic complexă cu o mult mai bună bază statistică,
permițând modelarea complexă a proceselor evolutive. Un mare dezavantaj este că
ML este foarte înceată, în comparație cu metodele parsimoniei, luându-i zile întregi
pentru a rula mulțimi mari de date. Inferența filogenetică a probabilității maximale
a fost creată pe la mijlocul secolului al XX-lea, dar a rămas doar o banală metodă
pentru inferența filogenetică încă din 1990, atunci când puterea computațională a
ajuns din urmă cererile imense ale analizei ML. Noi algoritmi și implementări oferă
timpi de analiză pentru mulțimi mari de date, la dimensiuni acceptabile. Până când
aceste metode vor câștiga un accept global, va rămâne preferată parsimonia pentru
mulțimile extrem de mari de date, mai ales în cazul în care metoda bootstrap este
folosită în evaluarea încrederii rezultatelor.
O zonă în care parsimonia excelează este analiza datelor morfologice. Până
în prezent, modelele stohastice ale schimbărilor de caracter nu au fost disponibile
pentru datele nemoleculare. Noi metode descoperite de Paul Lewis fac aceleași
presupuneri ca și analiza parsimoniei, dar într-un context de probabilități. Încă nu
s-au implementat aceste modele, și în cazul în care nu se modifică, este necesară
43

modificarea mulțimilor de date existente.
Probabilitatea maximală a fost criticată că admite, implicit, o evoluție neutră
pe lângă modelul stohastic de evoluție. Acest caz nu este neapărat necesar: la fel
ca și parsimonia, admiterea unul model stohastic nu presupune că toată evoluția
este stohastică. În practică, probabilitatea devine complexă din cauza deviațiilor
caracterelor aleatorii. Probabilitatea lucrează bine și cu secvențele de codificare ce
includ poziții gata să fie selectate.
O obiecțiune adusă de partizanii parsimoniei, este faptul că evoluția este prea
complexă sau nu este înțeleasă deloc pentru a fi modulată. Această obiecție se
bazează pe faptul că nu se înțelege termenul de “modelare”. Fiindu-ne mai simplu să
ne gândim că modelele reprezintă mecanică unui proces, tot nu observăm adevăratul
caz. De fapt, un model este selectat nu pentru reproducerea loială a fenomenului,
ci pentru abilitatea sa de a face prognozări. În practică, nu trebuie să încercăm și
să adaptăm exact un model la un proces, fiindcă există un schimb între numărul
de parametrii dintre un model și puterea lui statistică. Procesul stohastic se poate
adapta foarte bine la datele evolutive, la un nivel înalt, chiar dacă nu oglindește
exact în detaliu acest proces.
Prin analogie, piciorul uman nu numai că variază în lungime și lățime, dar com-
binațiile diferite ale valorilor lungimii și lățimii pot fi grupate pentru a corespunde
unei mari varietăți de picioare. În unele cazuri, un picior puțin mai mare decât cel
normal s-ar potrivi prin creșterea dimensiunii generale decât creșterea lățimii scobi-
turii gleznei, în timp ce un picior cu un călcâi mai îngust s-ar potrivi cu scobitura
gleznei mai lată și cu un pantof mai mic. Adăugarea mai multor măsuri va îmbună-
tăți cumva potrivirea cu pantoful, dar ar fi nepractică din punct de vedere al afacerii.
Cu o potrivire extrem de precisă, diferențele de picior ar face ca vânzarea perechilor
de pantofi adaptate să fie imposibilă, iar diferențele în timp ar însemna ca o potrivire
44

adecvată la cumpărare să nu mai corespundă cu cea la purtarea pantofilor.
S-a arătat recent că parsimonia ar fi probabilă să recupereze arborele corect în
cadrul schimbărilor drastice din parametrii evolutivi din cadrul unui arbore. Acest
lucru devine dificil de realizat, din moment ce astfel de schimbări sunt extrem de
semnificative în divergențele intense. Probabilitatea a avut rezultate complexe foarte
bune în recuperarea filogeniilor virale in vitro, în filogeniile simulate și în cele con-
firmate de alte metode. Atunci când apar mai multe divergențe superficiale, se pare
că această potențială complicație nu eronează prea mult rezultatele. În prezent,
mai multe grupuri de cercetători caută să includă inversările dramatice în parametri
evolutivi din cadrul analizei probabilităților.
Influența filogenetică bayesiană
Filogenetica bayesiană folosește funcția de probabilitate și este implementată
în mod normal, utilizând aceleași modele de schimbări evolutive din probabilitatea
maximală. Totuși, este destul de diferită, și în teorie, dar și în aplicații. Analiza
filogenetică bayesiană folosește teorema lui Bayes, ce leagă probabilitatea aposteriori
a unui arbore de probabilitatea datelor, folosind probabilitatea apriori a arborelui
și modelul de evoluție. Totuși, față de parsimonie și de metodele de probabilitate,
analiza bayesiană nu produce niciun arbore și nicio mulțime de arbori egal optimali.
Analiza bayesiană folosește probabilitatea arborilor într-o simulare Monte Carlo a
lanțului Markov, pentru eșantionarea arborilor în funcție de probabilitatea lor, astfel,
formând un eșantion de arbori convenabili.
Dezavantajul analizei bayesiene este nevoia de a delimita în mod explicit un set de
probabilități apriori pentru varietatea de valori de ieșire potențiale. Ideea incluziunii
probabilităților apriori într-o analiză a fost văzută ca o sursă potențială de erori.
Metodele bayesiene implică alte probleme, cum ar fi: evaluarea “convergenței”, care
45

este punctul în care procesul MCMC se oprește din căutarea “spațiului” de soluții
convenabile și începe să se formeze eșantionul credibil.
Metodele matricei distanțelor
Metodele fără parametri ale distanțelor au fost, inițial, aplicate în datele omolog
grupate, folosind o matrice de perechi de distanțe. Aceste distanțe sunt, apoi, unite
pentru a forma arborele (cu lungimi de ramuri informative). Matricea distanțelor
rezultă dintr-un număr de surse diferite, cum ar fi: distanța măsurată (de exemplu,
din studiile imunologice), sau analiza morfometrică, diferite formule ale perechilor
de distanțe (de exemplu, distanța euclidiană) aplicate caracterelor morfologice dis-
crete, sau distanța genetică din secvență, din fragmentele de restrângere și din datele
allozime (enzime care reprezintă produsul genelor allele din cadrul aceleiași gene).
Pentru datele filogenetice de tip caracter, valorile brute ale distanțelor se calcu-
lează prin simpla măsurare a diferențelor de perechi din stările de caracter (distanța
Manhattan).
Există mulți algoritmi simpli care construiesc un arbore, direct din distanțele
perechilor, câțiva din aceștia fiind UPGMA și neighbor-joining (NJ), însă ei nu for-
mează neapărat cel mai bun arbore. UPGMA presupune un arbore ultrametric
(un arbore în care toate lungimile drumurilor de la rădăcină la frunze sunt egale).
Neighbor-Joining este o formă de descompunere de stea și poate fi rapid în a forma
arbori convenabili. Acest algoritm se folosește de unul singur și chiar, deseori, pro-
duce arbori rezonabili.
Estimarea filogeniei folosind metodele cu distanțe a dus la foarte multe contro-
verse. Legătura dintre caracterele individuale și arbore se pierde în cadrul procesului
de reducere a caracterelor la distanțe. Din moment ce aceste metode nu folosesc în
mod direct datele de tip caracter, informația blocată în distribuirea stărilor de ca-
46

racter se poate pierde atunci când perechile se compară între ele. De asemenea,
unele legături filogenetice complexe pot duce la distanțe eronate. În ciuda acestor
potențiale probleme, metodele cu distanțe sunt extrem de rapide și, deseori, eva-
luează rezonabil filogenia. Ele au câteva avantaje față de metodele ce folosesc în
mod direct caracterele. Ceea ce este remarcabil este faptul că metodele cu distanțe
permit utilizarea datelor ce nu se pot converti ușor în date de tip caracter, cum sunt
testele de hibridizare ADN-ADN.
Probabilitatea maximală
Metodele de probabilitate maximală combină modelele statistice cu datele evo-
lutive deja cunoscute. Acestea sunt folosite pentru a prezice aspectele interesante și
realiste – analiza caracterului și a perioadelor de timp, secvențele speciilor dispărute
(din punct de vedere ipotetic) – însă numai la o complexitate mărită.
47

Capitolul 4
Aplicatie concretă: implementarea
unui algoritm de determinare a
arborilor filogenetici
Programul implementat compară mai multe secvențe genetice și generează o ma-
trice a distanțelor Levenstein (distantele de editare), precum și un graf de filogenie,
reprezentat prin mulțimea de clustere generată de algoritmul UPGMA (Unweighted
Pair Group Method using arithmetic Averages ) descris în Secțiunea 3.2.1.
Distanța între două secvențe genetice utilizată în program a fost distanța de
ediatre: Distanta Levenshtein (LD), care e o masura de similitudine intre doua
siruri, șirul sursa (s) si șirul de țintă (t). Distanta este numarul de ștregeri, inserții
sau substituții necesare pentru a transforma (s) în (t).
Pentru a calcula distanța Levenstein se inițializează o matrice a distantelor D:
Initializare : D(i,0) = i;
iar apoi se calculeazaă
48

Iteratie : D(i; j) =min8
>>>>>><
>>>>>>:0
D(i1; j) + 1
D(i; j1) + 1
D(i1; j1) +cost
unde cost este funcția de potrivire ( cost = 0pentru potrivire și cost = 1pentru
nepotrivire). Dist
Valoarea distanței se determină prin citirea elementului din dreapta
jos ([5]).
Aplicația a fost scrisă în Dev C++, având o interfață simplă, partea din stânga
fiind rezervată pentru introducerea secvențelor genetice, iar partea din dreapta re-
prezentând zona de afișare a grafului final de filogenie. După introducerea datelor,
matricea distanțelor Levenstein este afișată, precum i ¸ ansamblul clusterelor, pe mă-
sură ce sunt determinate.
Figura 4.1: Ecranul de execuție a aplicației
Codurile genetice au fost reținute într-o matrice alocată dinamic:
49

char* readString(int *n){
char *sir;
printf("\nDati lungimea codului ADN: ");
scanf("%d", n);
sir = (char*)malloc(sizeof(char) * (*n + 1));
printf("\n Introduceti elementele codului ADN ");
scanf("%s", sir);
return sir;
}
char** Alloc(int lin, int col) {
char** p_mat;
p_mat = (char**)malloc(lin * sizeof(char*));
for(int i = 0; i< lin; i++) {
p_mat[i] = (char*)malloc(sizeof(char) * (col + 1));
}
return p_mat;
}
…
matrice = Alloc(nr+1, NMAX);
for(i = 1; i <= nr; i++) {
50

printf("Pentru codul nr %d \n", i);
char* sir = readString(&n);
strcpy(cod[i], sir);
strcpy(matrice[i], sir);
Distanțele dintre secvențele genetice sunt calculate prin programare dinamică,
folosind funcția:
int levenstein (int i1, int j1)
{
int k,s, d[41][41], n1,n2;
char car1, car2;
int cost=1;
n1=strlen(matrice[i1]);
n2=strlen(matrice[j1]);
for(k = 0; k <= n1; k++)
d[k][0]=k;
for(k = 0; k <= n2; k++)
d[0][k]=k;
for(k = 1; k <= n1; k++)
{ car1=matrice[i1][k];
for(s = 1; s <= n2; s++)
{ car2=matrice[j1][s];
if (car1==car2) cost=0;
else cost=1;
51

d[k][s] = minimum(d[k-1][s]+1, d[k][s-1]+1, d[k-1][s-1] + cost);
};
};
return d[n1][n2];
}
pentru compararea secvențelor ișij.
Clusterele obținute sunt salvate într-un vector de șiruri Cl[][], fiecare șir con-
ținând pe prima poziție un marcator de selectare a clusterului (dacă face sau nu
parte dintr-un cluser mai mare), iar pe restul pozițiilor elementele clusterului. Nu-
mărul de elemente din clusterul ia fost reținut în NrEl [i]. O matrice de legături
Grține minte pentru fiecare cluster din care 2 clustere mai mici a fost creat, astfel
încât se poate genera arborele filogenic binar final.
Matricea Mconține la fiecare etapă a algoritmului distanțele dintre clustre, cal-
culate ca medii aritmetice ale distanțelor dintre elementele componente. La fiecare
pas, algoritmul determină care element al matricii M, corespunzând distanțelor
dintre clustere ne-incluse în alt cluster, este minimal, iar cele două clustere cores-
pondente mini șiminj se reunesc într-un cluster mai mare.
Codul surspentru implementarea algoritmului este dat mai jos.
float calculd(int a, int b)
{int i3,j3;
float sum=0.0;
for(i3 = 1; i3 <= NrEl[a]; i3++)
for(j3 = 1; j3 <= NrEl[b]; j3++) sum=sum+M[Cl[a][i3] ][ Cl[b][j3]];
52

return sum/NrEl[a]*NrEl[b] ;
}
……………………………
// UPGMA
for(i = 1; i <= nr; i++)
for(j = 1; j <= nr; j++)
dist[i][j]=levenstein(i,j);
for(i = 0; i < 100; i++)
for(j = 0; j < 100; j++)
M[i][j]=10000.0; //matricea algoritmului UPGMA
for(i = 1; i <= nr; i++)
for(j = 1; j <= nr; j++)
M[i][j]=dist[i][j];
printf("\n Distantele de editare intre acestea sunt \n");
for(i = 1; i <= nr; i++)
{
for(j = 1; j <= nr; j++) printf(" %d", dist[i][j]);
printf("\n");
}
//initializare graf: gr[k][.]=s reprezinta o muchie orientata top down (s->k)
NrCl=nr;//clustere initiale
53

NrUn=nr; //neselectate
for(i=1;i<=nr; i++) {
Gr[i][0]=1; // 1=frunza, 0= nod
Gr[i][1]=0; // fara alte nivele inferioare
Gr[i][2]=0;
Cl[i][0]=0; //neselectat
NrEl[i]=1;
Cl[i][1]=i;
};
nod=0;
for(int k=NrUn;k>1;k–)
{ printf("\n NrCl= %d NrUn=%d", NrCl,NrUn);
mi=10000.0;
mini=0;
minj=0;
for(i=1;i<=NrCl;i++)
{
if( (Cl[i][0]==0) )
{ for (j=1;j<=nr; j++)
if(i!=j)
if (mi > M[i][j] )
{ mi=M[i][j];
mini=i; minj=j;
54

};
};
};
//creare de nou Cluster
NrCl++; nod++;
Cl[NrCl][0]=0;
NrEl[NrCl]= NrEl[mini]+NrEl[minj];
for(i2=1;i2<=NrEl[mini];i2++) Cl[NrCl][i2]=Cl[mini][i2];
for(i2=1;i2<=NrEl[minj];i2++) Cl[NrCl][i2+NrEl[mini] ]=Cl[minj][i2]; //copiere elemente
Cl[mini][0]=1; //selectat
Cl[minj][0]=1;
Gr[i][0]=0; // 1=frunza, 0= nod
Gr[NrCl][1]=mini; // fara alte nivele inferioare
Gr[NrCl][2]=minj;
NrUn=NrUn-1;
//determinare distante
for(j2=1;j2<NrCl;j2++)
M[NrCl][j2]= calculd(NrCl,j2);
};//end while
//afisare
for(i=1;i<=NrCl;i++)
55

{printf("\n Clusterul %d : ",i);
for(j=1;j<=NrEl[i];j++)
printf(" %d", Cl[i][j]);
};
56

Capitolul 5
Concluzii
În lucrare s-au prezentat pe scurt teoria evoluției moleculare a speciilor, analizându-
se date de secvențe ADN și determinându-se relațiile dintre și între specii cu ajutorul
arborilor filogenetici.
Am evidențiat procesul de selecție naturală în populații. Am studiat două mo-
dele probabilistice de divergență: Jukes-Cantor și Kimura și am discutat despre doi
algoritmi, UPGMA și Neighbor-Joining, cu care se pot construi arbori de gene, fo-
losind date relaționale. Am descris procesul de asemănare și de înrudire a speciilor.
Am pus în discuție modelarea evoluției prin procesele de mutație și prin folosirea a
trei tipuri de arbori: cladograma, filograma și arborele ultrametric.
Am intrat de asemenea în studiul parsimoniei, descriind procesele de înregistrare,
de urmărire și de implementare prin etape succesive. U
În final am descris o implementare în C++ a algoritmului UPGMA ( Unweighted
Pair Group Method using arithmetic Averages ) de construcție a arborilor filogenetici
prin metoda distanțelor medii.
57

Bibliografie
[1] David W. Mount, Bioinformatics. Sequence and Genome Analysis, Second Edi-
tion, 2004, Cold Spring Harbor Laboratorry Press, Cold Spring Harbor, New
York
[2] Ron D. Appel, Ernest Feytmans, Bioinformatics. A Swiss Perspective, 2009,
World Scientific Publishing Co. Pte. Ltd. and the Swiss Institute of Bioinfor-
matics
[3]http :==en:wikipedia:org=wiki=Molecular _evolution
[4]http :==en:wikipedia:org=wiki=Parsimony _analysis
[5] R. Bellman. Dynamic Programming . Princeton University Press, 1957.
58