20 Pages
English

Algorithms for exploring the space of gene tree species tree reconciliations

Gain access to the library to view online
Learn more

Description

Niveau: Supérieur, Doctorat, Bac+8
Algorithms for exploring the space of gene tree/species tree reconciliations (Technical report _1323) Jean-Philippe Doyon2, Cedric Chauve1, and Sylvie Hamel2 1 Department of Mathematics, Simon Fraser University, 8888 University Drive, V5A 1S6, Burnaby (BC), Canada, 2 DIRO, Universite de Montreal, CP6128, succ. Centre-Ville, H3C 3J7, Montreal (QC),Canada, [hamelsyl,doyonjea]@iro.umontreal.ca Abstract. We describe algorithms to explore the space of all possible reconciliations between a gene tree and a species tree. We propose an algorithm for generating a random reconciliation, and combinatorial op- erators and algorithms to explore the space of all possible reconciliations between a gene tree and a species tree in optimal time. We apply these algorithms to simulated data. 1 Introduction Genomes of contemporary species, especially eukaryotes, are the result of an evolutionary history, that started with a common ancestor from which new species evolved through evolutionary events called speciations. One of the main objectives of molecular biology is the reconstruction of this evo- lutionary history, that can be depicted with a rooted binary tree, called a species tree, where the root represents the common ancestor, the internal nodes the ancestral species and speciation events, and the leaves the ex- tant species.

  • tree mapping

  • circles represent

  • duplication

  • species tree

  • ancestral species

  • evolutionary genomics

  • eukaryotic genes

  • gene tree


Subjects

Informations

Published by
Reads 14
Language English
Algorithmsforexploringthespaceofgenetree/speciestreereconciliations(Technicalreport#1323)Jean-PhilippeDoyon2,CedricChauve1,andSylvieHamel21DepartmentofMathematics,SimonFraserUniversity,8888UniversityDrive,V5A1S6,Burnaby(BC),Canada,cedric.chauve@sfu.ca2DIRO,Universite´deMontre´al,CP6128,succ.Centre-Ville,H3C3J7,Montre´al(QC),Canada,[hamelsyl,doyonjea]@iro.umontreal.caAbstract.Wedescribealgorithmstoexplorethespaceofallpossiblereconciliationsbetweenagenetreeandaspeciestree.Weproposeanalgorithmforgeneratingarandomreconciliation,andcombinatorialop-eratorsandalgorithmstoexplorethespaceofallpossiblereconciliationsbetweenagenetreeandaspeciestreeinoptimaltime.Weapplythesealgorithmstosimulateddata.1IntroductionGenomesofcontemporaryspecies,especiallyeukaryotes,aretheresultofanevolutionaryhistory,thatstartedwithacommonancestorfromwhichnewspeciesevolvedthroughevolutionaryeventscalledspeciations.Oneofthemainobjectivesofmolecularbiologyisthereconstructionofthisevo-lutionaryhistory,thatcanbedepictedwitharootedbinarytree,calledaspeciestree,wheretherootrepresentsthecommonancestor,theinternalnodestheancestralspeciesandspeciationevents,andtheleavestheex-tantspecies.Othereventsthanspeciationcanhappen,thatdonotresultimmediatelyinthecreationofnewspeciesbutareessentialineukaryoticgenesevolution,suchasgeneduplicationandloss[12].Duplicationisthegenomicprocesswhereoneormoregenesofasinglegenomearecopied,resultingintwocopiesofeachduplicatedgene.Geneduplicationallowsonecopytopossiblydevelopanewbiologicalfunctionthroughpointmu-tation,whiletheothercopypreservesitsoriginalrole.Ageneissaidtobelostwhenithasnofunctionorisfullydeletedfromthegenome.(See[12]forexample).Othergenomiceventssuchaslateralgenetransfer,thatoccursmostlyinbacterialgenomes,willnotbeconsideredhere.Genesofcontemporaryspeciesthatevolvedfromacommonancestor,throughspeciationsandduplications,aresaidtobehomologs[9]andaregroupedintoagenefamily.Theevolutionofagenefamilycanbedepictedwitha
rootedbinarytree,calledagenetree,wheretheleavesrepresenttheho-mologouscontemporarygenes,theroottheircommonancestralgeneandtheinternalnodesrepresentancestralgenesthathaveevolvedthroughspeciationsandduplications.GivenagenetreeGandthespeciestreeofthecorrespondinggenomesS,animportantquestionistolocateinStheevolutionaryeventsofspe-ciationsandduplications.AreconciliationbetweenGandSisamappingofthegenes(extantandancestral)ofGontothenodesofSthatinducesanevolutionaryscenario,intermsofspeciations,duplicationsandlosses,forthegenefamilydescribedbyG.Inthisperspective,thenotionofrec-onciliationwasfirstintroducedinthepioneeringworkof[10]andafirstformaldefinitionwasgivenin[17]toexplainthediscrepanciesbetweengenesandspeciestrees.TheLCA-mapping,thatmapsageneuofGontothemostrecentspeciesofSthatisancestorofallgenomesthatcontainagenedescendantofu,isthemostwidelyusedmapping,asitdepictsaparsimoniousevolutionaryprocessaccordingtothenumberofdupli-cationsorduplicationsandlossesitinduces.Itiswidelyacceptedthatparsimonyisapertinentcriterioninevolutionarybiology,butthatitdoesnotalwaysreflectsthetrueevolutionaryhistory.Thisleadtothedefini-tionofmoregeneralnotionsofreconciliationsbetweenagenetreeandaspeciestree[2,11,1]andthenaturalproblemofexploringnon-optimal(foragivencriterion)reconciliations,andthenalternativeevolutionaryscenariosforgenefamilies.Themainconcernofourworkisthedevelopmentofalgorithmsforex-ploringthespaceofthereconciliationsbetweenagenetreeandaspeciestree.Afterintroducingaverygeneralnotionofreconciliation(Section2),wedescribeinSection3analgorithmthatgeneratesarandomreconcil-iationundertheuniformdistribution,inSection4.1combinatorialoper-atorsthataresufficienttoexplorethecompletespaceofreconciliationsbetweenagenetreeandaspeciestree,andinSection4.2analgorithmthatexploresexhaustivelythisspaceandcomputesinoptimaltimethedistributionofreconciliationscoresintheduplication,loss,andmutation(duplication+loss)costmodels.(Allproofswillbegiveninafuturetechnicalreport[6]).Thereareseveralapplicationsofouralgorithmsinfunctionalandevolutionarygenomics,suchasinferringorthologsandparalogs[8,14],thegenecontentofanancestralgenome[16],orinthecontextofMarkovChainMonteCarloanalysisofgenefamilies[1].WeillustrateouralgorithmswithexperimentsonsimulatedgenefamiliesinSection5computedusingduplicationandlossratestakenfrom[13].Our