Models algebraics en filogenètica

Butllet´ ı de la Societat Catalana de Matem` atiques Vol. 00, n´um. 0, 2006. P`ag. 1–5 Models algebraics en filogen`etica∗ Marta Casanellas Mathematics is biology’s next microscope, only better; biology is mathematics’ next physics, only better. Joel E. Cohen Resum En aquest article fem una introducci´o a les aplicacions de la geometria algebraica en filogen`etica. Gr`acies a qu`e gran part dels models evolutius usats en filogen`etica corresponen a varietats algebraiques, l’ideal associat a aquestes varietats pot ser usat per donar un nou enfocament a la infer`encia filogen`etica. Paraules clau: invariants filogen`etic, model evolutiu, aplicaci´o racional Classificaci´o MSC2000: 14M25, 92D15, 92D20 Resum en angl`es: In this paper we present some applications of algebraic geometry to phylogenetics. As many of the evolutionary models correspond to algebraic varieties, it is possible to use the ideal associated to these varieties for phylogenetic inference. Paraules clau en angl`es: phylogenetic invariant, evolutionary model, rational map. 1 Introducci´o En els darrers anys s’ha demostrat que dues disciplines tan distants com la geometria algebraica i la gen`etica comparativa poden beneficiar-se d’un treball conjunt. Aquestes dues `arees es poden connectar gr`acies a l’estad´ıstica algebraica, ∗Aquesta exposici´o correspon a la xerrada impartida per la mateixa autora a la Novena Trobada de la Societat Catalana de Matem`atiques que va tenir lloc a Vic el 22 d’abril de 2006. 2Marta Casanellas que parteix del fet que un gran nombre de models estad´ıstics usats en biologia corresponen a varietats algebraiques. L’estad´ıstica algebraica s’ha desenvolupat en els ´ultims anys i s’ha aplicat a l’estudi de taules de conting`encia, disseny d’experiments....(veure [15]). Recentment, s’han unit esfor¸cos de bi`olegs i ge`ometres algebraics per a incidir en les aplicacions de l’estad´ıstica algebraica a la biologia computacional. Els fruits d’aquest esfor¸c els podem trobar per exemple al llibre “Algebraic statistics for computational biology” [14]. En aquest a article pretenem fer una introducci´o a la relaci´o entre la geometria algebraica i la gen`etica, o m´es concretament la filogen`etica. Com veurem, l’´us de la geometria algebraica en la filogen`etica pot aportar noves t`ecniques i nous resultats a aquesta branca de la biologia. La filogen`etica parteix de la base que tots els organismes de la Terra prov´enen d’un ancessor com´u. Aix´ı, totes les esp`ecies de la Terra tenen relacions ancestrals entre elles que s’anomenen filog`enies. Les filog`enies es poden representar mitjan¸cant un arbre denominat arbre filogen`etic. En particular, la filogen`etica es dedica a inferir aquests arbres a partir dels genomes1de les esp`ecies que trobem en l’actualitat. L’arbre filogen`etic es dibuixa com una arbre invertit: les fulles de l’arbre representen les esp`ecies actuals i les situem a baix de tot; l’arrel de l’arbre filogen`etic es troba al node de dalt de tot i representa l’ancessor com´u de totes les esp`ecies que formen l’arbre, i els nodes interiors representen esp`ecies ancestrals comuns de les esp`ecies que se’n deriven. La longitud de les branques representa la “dist`ancia evolutiva” entre les esp`ecies que uneix la branca o, dit d’una altra manera, el nombre de mutacions que s’han produ¨ıt entre el node pare i el node fill. Per exemple, si coneixem el genoma —o part d’ell (normalment s’usen nom´es els gens)— de l’esp`ecie humana, el ximpanz´e i el goril.la, podem preguntar-nos quin ´es l’arbre filogen`etic d’aquestes esp`ecies. Tenim tres possibilitats representades en la figura 1. hum`a goril.la ximp (1) goril.la ximp hum`a (2) ximp goril.la hum`a (3) Figura 1:Els tres possibles arbres de tres fulles Fins als anys 80 es creia que l’arbre correcte era el primer, per`o des que s’han fet estudis usant els genomes de les esp`ecies, hi ha for¸ca evid`encies que l’arbre que ha donat lloc a l’esp`ecie humana ´es el segon (veure [2]). En aquest article presentarem, 1 El genoma d’una esp`ecie eucariota ´es el contingut d’ADN que trobem en el nucli de les c`el.lules. Les unitats b`asiques que composen l’ADN s´on els nucle`otids. Hi ha quatre nucle`otids diferents: Adenota adenina,Ccitosina,Gguanina iTtimina. En el nostre context, donar el genoma d’una esp`ecie equival a donar una seq¨u`encia ordenada de car`acters en les lletres A,C,G,T. Models algebraics en filogen`etica 3 des d’un punt de vista esbiaixat vers la geometria algebraica, el tipus d’estudis en filogen`etica que han donat lloc a aquestes conclusions. En la seg¨uent secci´o farem una introducci´o als models estad´ıstics m´es usats en filogen`etica i n’estudiarem la relaci´o amb la geometria algebraica. En la secci´o 3 presentarem els resultats de geometria algebraica que permeten donar un nou enfocament a la infer`encia filogen`etica. Finalment a la secci´o 4 donarem m`etodes que demostren que a la pr`actica s´ı que ´es factible usar les t`ecniques de geometria algebraica per a reconstrucci´o d’arbres filogen`etics. 2 Models algebraics en filogen`etica 2.1 Models estad´ıstics d’evoluc´o Per a representar el proc´es evolutiu de la formaci´o d’esp`ecies donarem un model estad´ıstic basat en les mutacions que es produeixen en l’ADN, on suposarem que: (i) Els arbres s´on binaris, ´es a dir, del node arrel en surten dues branques i cada branca es divideix en dues m´es fins arribar a les fulles. (ii) L’evoluci´o d’una esp`ecie nom´es dep`en del node immediatament superior. (iii) Les mutacions ocorren aleat`oriament i la probabilitat que es produeixi una mutaci´o ´es sempre positiva. (iv) Suposarem donat un alineament de les seq¨u`encies d’ADN de les esp`ecies. Degut a processos de mutaci´o, duplicaci´o i supressi´o de parts de l’ADN, les seq¨u`encies de les diferents esp`ecies tenen parts id`entiques, parts que s’assemblen i parts que no es poden comparar. A m´es a m´es les parts id`entiques o comparables no tenen per qu`e trobar-se en el mateix lloc del genoma (els genomes de diferents esp`ecies tenen diferents longituds i diferent nombre de cromosomes i de gens). ´ Es per aix`o que abans d’estudiar les relacions entre les esp`ecies ens interessa saber quines parts de l’ADN s´on comparables i quines parts dels genomes de les diferents esp`ecies es corresponen entre elles. Tot aix`o es recull en un bon alineament de les seq¨u`encies d’ADN que volem considerar. En el nostre exemple, suposarem que partim del seg¨uent alineament de seq¨u`encies: hum`a AACTTCGAGGCTTACCGCTG goril.la AACGTCTATGCTCACCGATG ximpanz´e AAGGTCGATGCTCACCGATG (v) Les diferents posicions de la cadena d’ADN evolucionen de la mateixa manera i independentment de les altres posicions. Com que suposem que totes les posicions de la cadena d’ADN evolucionen de la mateixa manera, per a cada posici´o considerarem el mateix model evolutiu probabil´ıstic que representarem en l’arbre de la seg¨uent forma. Enumerem els v`ertexos de l’arbre d’esquerra a dreta i de baix a dalt i anomenem tia la longitud de la branca que puja des del v`ertex i. El node arrel s’anomenar`a r. A cada v`ertex ide l’arbre 4Marta Casanellas hi posem una variable aleat`oria discreta que pren valors a {A,C,G,T}. Les variables aleat`ories Xia les fulles de l’arbre seran “variables observades” (perqu`e l’alineament ens d´ona observacions del vector aleatori X= (X1, X2, X3)), les dels nodes interiors seran ocultes (perqu`e no en tindrem cap observaci´o) i les anomenarem Yi: Figura 2:Model estad´ıstic en un arbre de tres fulles Seguint un proc´es de Markov, a cada branca li associem una matriu Siles entrades de la qual s´on les probabilitats P(x|y, ti) que un nucle`otid yen el node pare muti a un nucle`otid xen el node fill al llarg d’una branca de longitud ti: A C G T Si= A C G T     P(A|A, ti)P(C|A, ti)P(G|A, ti)P(T|A, ti) P(A|C, ti)P(C|C, ti)P(G|C, ti)P(T|C, ti) P(A|G, ti)P(C|G, ti)P(G|G, ti)P(T|G, ti) P(A|T, ti)P(C|T, ti)P(G|T, ti)P(T|T, ti)     Aquestes probabilitats s´on desconegudes per a nosaltres i seran els par`ametres del model. Les matrius Sis’anomenen matrius de substituci´o. Suposarem que la distribuci´o de nucle`otids en l’arrel πA=P(Yr=A), πC= P(Yr=C), πG=P(Yr=G), πT=P(Yr=T) ´es coneguda. La hip`otesi (v) ens diu que la probabilitat que del node arrel de l’arbre (1) de la figura 1 s’hagi evolucionat a les seq¨u`encies d’hum`a, goril.la i ximpanz´e donades en l’alineament ´es igual a p4 AAA ∗pCCG ∗pTGG ∗p3 TTT ∗p4 CCC ∗pGTG ∗pGTT ∗p3 GGG ∗pTCC ∗pCAA on px1x2x3=P(X1=x1, X2=x2, X3=x3). Dit d’una altra manera, la hip`otesi (v) ens diu que les columnes de l’alineament evolucionen de forma independent. Considerant el proc´es de Markov en l’arbre de la figura 2, la probabilitat d’observar els nucle`otids x1, x2, x3en les fulles s’expressa en funci´o de les entrades de les matrius de substituci´o de la seg¨uent manera: px1x2x3=X yr,y4∈{A,C,G,T} πyrS1(x1, yr)S4(y4, yr)S2(x2, y4)S3(x3, y4).(1) Tenim diferents models estad´ıstics d’evoluci´o segons la forma que tinguin les matrius de substituci´o i segons la distribuci´o de nucle`otids en l’arrel. Seguidament els presentem en la seva versi´o algebraica (veure secci´o 2.2). Models algebraics en filogen`etica 5 Models de grup. Els models m´es usats en filogen`etica s´on els models de grup (a la seg¨uent secci´o veurem per qu`e s’anomenen aix´ı). En aquests models la distribuci´o de nucle`otids en l’arrel ´es uniforme i les matrius de substituci´o s´on de la forma Si=     aibicidi biaidici cidiaibi dicibiai     on ai+bi+ci+di= 1. La justificaci´o biol`ogica per a aquest model rau en el fet que, degut a certes propietats qu´ımiques, l’adenina i la guanina s´on purines i la citosina i la timina s´on pirimidines. Aquest model (anomenat Kimura 3- par`ametres [12]) vol reflectir el fet que les transicions (´es a dir, mutacions de purina a purina o pirimidina a pirimidina) s´on m´es freq¨uents que les transversions (mutacions de purina a pirimidina o a l’inversa). Casos particulars d’aquest model s´on el Kimura 2-par`ametres [11] (nom´es usa un par`ametre per a les transicions i un altre per a les transversions, ´es a dir bi=di) i el Jukes-Cantor [10] (´es el model m´es simple ja que no distingeix entre transicions i transversions, ´es a dir bi=ci=di). Strand symmetric model. En aquest model no se suposa que la distribuci´o de nucle`otids ´es uniforme sin´o que πA=πTiπC=πG. Aquest model s’adapta m´es a la realitat de les seq¨u`encies que s’usen normalment per a inferir filog`enies, que s´on seq¨u`encies codificants (gens o parts de gens). Les regions codificants contenen m´es C, G’s que no pas A,T’s i degut a la simetria de la doble cadena d’ADN, s’ha comprovat en diversos estudis que πA∼πTiπC∼πG. En aquest model suposarem que πA=πT iπC=πG. D’altra banda, si una Amuta a una C, aleshores en la cadena d’ADN complement`aria es produeix una mutaci´o de TaGperqu`e una A(respectivament C) sempre va enlla¸cada amb una T(resp. G). Aix´ı es natural requerir que P(A|A) = P(T|T), P(C|A) = P(G|T), P(G|A) = P(C|T), P(T|A) = P(A|T), P(A|C) = P(T|G), P(C|C) = P(G|G), P(G|C) = P(C|G), P(T|C) = P(T|G). Aquest model nom´es requereix aquestes igualtats i per tant les matrius de substituci´o s´on de la forma Si=     aibicidi eifigihi higifiei dicibiai    . Notem que els models de grup s´on un cas particular d’aquest. Aquest model algebraic va ser introdu¨ıt a [5]. 6Marta Casanellas Model de Markov general. Aquest ´es el model m´es general possible. No es requereix res sobre la distribuci´o en l’arrel i les matrius de substituci´o s´on gen`eriques: Si=     aibicidi eifigihi jikilimi nioipiqi    . Un model amb m´es par`ametres sempre s’adequa m´es a la realitat per`o augmentar el nombre de par`ametres pot augmentar molt´ıssim la complexitat dels c`alculs necessaris per a inferir filog`enies. 2.2 Invariants filogen`etics Els models evolutius que hem descrit s´on models algebraics. S’anomenen aix´ı perqu`e les probabilitats conjuntes de les variables observades s’expressen com a funci´o polin`omica en els par`ametres (veure equaci´o (1)). Aix´ı, un model evolutiu algebraic de dpar`ametres lliures sobre un arbre Tde nfulles ve descrit per la seg¨uent aplicaci´o polinomial: ϕ:Rd−→ R4n θ= (θ1, . . . , θd)7→ (pAA...A, pAA...C, pAA...G, . . . , pTT...T)(2) Per exemple, si en el seg¨uent arbre considerem el model de Jukes-Cantor, obtenim (substituint en l’equaci´o (1)): pAAA =1 4(a1a4a2a3+ 3b1b4a2a3+ 3b1a4a2a3+ 3a1b4a2a3+ 6b1b4b2b3),(3) on ai+ 3bi= 1.Observem que per a qualsevol dels models descrits, px1x2x3´es un polinomi homogeni de grau igual al nombre de branques de l’arbre. En el cas del model de Jukes-Cantor, per a un arbre de tres fulles tenim definida una aplicaci´o polin`omica ϕ:R4−→ R64 (a1, a2, a3, a4)7→ (pAAA, pAAC, pAAG, . . . , pTTT) Models algebraics en filogen`etica 7 De fet, com que estem parlant de probabilitats, el model estad´ıstic est`a definit a ∆1×∆1×∆1×∆1i la imatge de l’aplicaci´o polinomial ha de caure dins del s´ımplex de dimensi´o 63, ∆63. L’aplicaci´o polinomial (2) parametritza un obert d’una varietat algebraica. Recordem que una varietat algebraica ´es el conjunt de punts que s´on soluci´o d’un sistema d’equacions polinomials: V=Z(f1, . . . , fr), f1, . . . , fr∈k[x1, . . . , xn], on k´es un cos. La imatge d’una aplicaci´o polinomial no ´es en general una varietat algebraica, per`o sempre podem considerar la seva clausura, ´es a dir, la menor varietat algebraica que el cont´e. Les varietats algebraiques s´on els tancats d’una topologia en knanomenada topologia de Zariski. A partir d’ara quan parlem de la imatge d’una aplicaci´o polinomial ϕens referirem a la seva clausura. Aix´ı Im(kd) denotar`a la menor varietat algebraica que cont´e ϕ(kd). Quan el cos k´es infinit es pot veure que aquesta varietat algebraica ´es irreductible. Per a poder estudiar una varietat algebraica ens interessa con`eixer els generadors del seu ideal. Recordem que donat un subconjunt Xde kn, l’ideal de X´es el conjunt de polinomis que s’anul.len sobre tots els punts de X, I(X) = {f(x1, . . . , xn)|f∈k[x1, . . . , xn], f(p) = 0 ∀p∈X}. Es pot demostrar f`acilment que I(X) ´es un ideal de l’anell de polinomis k[x1, . . . , xn]. El teorema de la base de Hilbert ens diu que aquest anell ´es noetheri`a i per tant, tot ideal ´es finitament generat. Aix´ı existeixen generadors g1, . . . , gs∈k[x1, . . . , xn] tals que I(X) = (g1, . . . , gs). Degut al teorema dels zeros de Hilbert, sovint ens interessa considerar les nostres varietats dins de Cn. De fet, en els casos que es pugui, ´es molt m´es pr`actic considerar els models estad´ıstics com aplicacions racionals des d’un producte d’espais projectius en un altre espai projectiu. Tornant a l’aplicaci´o polinomial (2) definida per un model evolutiu, ens interessa trobar els generadors de l’ideal de la clausura de la imatge. 1 Definici´ oSigui Vla clausura de la imatge de l’aplicaci´o ϕassociada a un arbre Tde nfulles i a un model evolutiu M. Els polinomis de I(V) s’anomenen invariants algebraics. Aquells polinomis de I(V) que no estan en l’ideal I(V0) corresponent a un altre arbre T0de nfulles sota el mateix model Ms’anomenen invariants filogen`etics. Els invariants filogen`etics permeten distingir entre diferents arbres i per tant poden ser usats per a inferir l’arbre filogen`etic d’esp`ecies actuals. Els invariants filogen`etics van ser introdu¨ıts per bi`olegs i han estat usats per a estudiar l’adequaci´o del model escollit o b´e per a deduir divisions ancestrals entre grups d’esp`ecies. Concretament van ser introdu¨ıts per Lake [13] i independentment per Cavender i Felsenstein [6]. No ha estat fins fa un parell d’anys que els matem`atics, o m´es precisament els ge`ometres algebraics, s’han interessat per aquesta aplicaci´o de la geometria algebraica. Exemple En el cas d’un arbre Tde 3 fulles sota el model de Jukes-Cantor les seg¨uents igualtats (que es dedueixen f`acilment de la simetria de les matrius de substituci´o en aquest model) donen lloc a invariants algebraics: 8Marta Casanellas pAAA =pCCC =pGGG =pTTT 4 termes pAAC =pAAG =pAAT =· · · =pTTG 12 termes pACA =pAGA =pATA =· · · =pTGT 12 termes pCAA =pGAA =pTAA =· · · =pGTT 12 termes pACG =pACT =pAGT =· · · =pCGT 24 termes Un altre invariant que trobem f`acilment ´es Px1,x2,x3px1x2x3−1 = 0. Aquests 60 invariants algebraics s´on polinomis de l’ideal per a qualsevol arbre de 3 fulles sota el model Jukes-Cantor i per tant no s´on invariants filogen`etics. Tenim 3 arbres possibles de 3 fulles (vegeu la figura 1) i l’´unic que els distingeix sota el model de Jukes-Cantor ´es un polinomi de grau 3. Per a cadascun dels tres arbres possibles l’ideal est`a generat pels 60 invariants lineals que hem donat i per un polinomi de grau 3 que es pot calcular usant un programa d’`algebra computacional (per exemple el SINGULAR [9]). Aix`o ens defineix una varietat de dimensi´o 3 a R64 (que viu de fet a R4). Per a arbres de 4 o m´es fulles ´es impossible usar un programa d’`algebra computacional per a trobar els generadors de l’ideal (fins i tot sota models senzills com Jukes-Cantor). Cal doncs, provar resultats te`orics que ens permetin trobar els generadors de l’ideal (vegeu la secci´o 3). A la p`agina web http://bio.math.berkeley.edu/ascb/chapter15/ hi ha descrits els invariants algebraics per a arbres de fins a 5 fulles i sota diferents models evolutius. Anomenem ρx1...xna la freq¨u`encia relativa de la n-tuple x1, . . . , xnen l’alineament donat. En l’exemple de Jukes-Cantor proposat en les p`agines 3 i 7, seguint l’arbre (1) de la figura 1 i l’alineament donat tenim que: ρAAA = 4/20, ρCAA = 1/20, ρCCC = 4/20, ρCCG = 1/20, ρGGG = 3/20 ρGTG = 1/20, ρGTT = 1/20, ρTCC = 1/20, ρTGG = 1/20, ρTTT = 3/20 i ´es 0 en els altres casos. En el cas hipot`etic que un conjunt de seq¨u`encies haguessin evolucionat seguint un arbre i un model evolutiu dels descrits aqu´ı, tindr´ıem que els invariants filogen`etics corresponents s’anul.larien quan els avalu´essim en les freq¨u`encies relatives ρx1...xn. Dit d’una altra manera, (ρAA...A, . . . , ρTT...T) seria un punt de la nostra varietat algebraica. a la pr`actica, les seq¨u`encies no han evolucionat seguint un model evolutiu i per tant en avaluar els invariants filogen`etics en les freq¨u`encies relatives de l’arbre correcte obtindrem valors nom´es propers a zero. Nota Acabem de veure que el model de Jukes-Cantor per a un arbre arrelat de tres fulles ens defineix una varietat algebraica de dimensi´o 3 a R64. En particular en aquest model els par`ametres no s´on identificables, ´es a dir, donat un punt de la varietat la seva antiimatge per ϕno consta d’un ´unic punt (a1, a2, a3, a4)∈R4, Models algebraics en filogen`etica 9 sin´o de tota una corba. En els models no algebraics, a l’hora d’inferir un arbre filogen`etic cal inferir tamb´e quina ´es la longitud de les branques de l’arbre. Si en el model que estem considerant els par`ametres no s´on identificables, aix`o implica que no podem trobar totes les longituds de les branques sin´o la suma d’algunes d’elles. En particular, no podem con`eixer quina ´es la longitud de les branques que van des de l’arrel fins als altres nodes. Per a tenir models identificables, cal parlar d’arbres sense arrel i ´es per aix`o que en la secci´o 4 considerem nom´es arbres sense arrel. 3 Invariants per als models basats en grups i generalitzacions Per a obtenir l’ideal de les varietats algebraiques corresponents als models de grup (Jukes-Cantor i Kimura 2 i 3 par`ametres) ha estat molt ´util fer un canvi de coordenades en les indeterminades px1...xn. El canvi proposat a [7] ´es una transformada de Fourier discreta tal i com describim a continuaci´o. Pensem els car`acters A,C,G,T com a elements del grup G=Z2×Z2. Aix´ı podem veure les matrius de substituci´o com a certes funcions sobre el grup: Si(g, h) = fi(h−g), g, h ∈G (´es f`acil deduir com ´es fsegons el model) i d’aquesta manera podem escriure les probabilitats conjuntes a les fulles tamb´e com a funcions sobre G×G× · · · × G: p(g1, . . . , gm) = 1 4X Y b∈branques fb(gp(b)−gf(b)) on la suma ´es sobre tots els possibles valors de les variables en els nodes interns de l’arbre (si b´es un abranca de l’arbre, p(b) denota el node pare de bif(b) el node fill). Recordem que si tenim una funci´o f:G−→ C, la seva transformada de Fourier discreta ˆ f:ˆ G=Hom(G, C∗)−→ Cve donada per ˆ f(χ) = X g∈G χ(g)f(g), χ ∈G∗. Una de les propietats m´es ´utils de la transformada de Fourier ´es que si tenim una convoluci´o de dues funcions (f1∗f2)(g) = Ph∈Gf1(h)f2(g−h), la seva transformada ´es el producte de transformades: \ f1∗f2=b f1·b f2. Aix´ı es va poder demostrar el seg¨uent teorema: 2 Teorema (Evans-Speed [7]) Per a un model basat en grup sobre un arbre T, la transformada de Fourier de la distribuci´o conjunta p(g1, . . . , gn)t´e la forma q(χ1, . . . , χm) = Y b∈branquesb fbY l∈fulla per sota de b χl Per tant, una expressi´o com (3) passa a ser una expressi´o monomial en les coordenades de Fourier. Dit d’una altra manera, en el cas dels models de grup,