Summary QDist is a program for computing the quartet
BIOINFORMATICSAPPLICATIONSNOTE
Vol.20no.102004,pages1636–1637

doi:10.1093/bioinformatics/bth097
QDist—quartetdistancebetweenevolutionarytrees
ThomasMailund andChristianN.S.Pedersen
BioinformaticsResearchCenter(BiRC),UniversityofAarhus,NyMunkegade,Building540,DK-8000ÅrhusC,Denmark
ReceivedonNovember18,2003;revisedandacceptedonNovember28,2003AdvanceAccesspublicationFebruary12,2004
ABSTRACT
Summary:QDistisaprogramforcomputingthequartetdistancebetweentwounrootedtrees,i.e.thenumberofquar-tettopologydifferencesbetweenthetrees,whereaquartettopologyisthetopologicalsubtreeinducedbyfourspecies.TheprogramisbasedonanalgorithmwithrunningtimeO(nlog2n),whichmakesitpracticaltocomparelargetrees.AvailableunderGNUlicense.
Availability:doc.guandang.net
thatre ectdifferentaspectsofbiology.Bryantetal.(2000)discussdifferentdistancemeasuresandconcludethatthequar-tetdistance(Estabrooketal.,1985)hasseveralattractiveproperties.Comparedwiththesplitdistance,onecansaythatthequartetdistancepenalizesedgesindividually,dependingonthestructureofthesubtreesconnectedbytheedge.Here,wepresentanimplementationofthealgorithminBrodaletal.(2001)forcomputingthequartetdistancebetweentwotreesofnspeciesintimeO(nlog2n)andspaceO(n).
2
1
INTRODUCTION
Theevolutionaryrelationshipforasetofspeciescanbedescribedbyarootedtreewhereleavescorrespondtothespe-cies,andtheinternalnodescorrespondtospeciationevents.Thedirectionoftheevolutionisdescribedbythelocationoftheroot,whichcorrespondstothemostrecentcom-monancestorforallthespecies,andtherateofevolutionisdescribedbyassigninglengthstotheedges.Estimatingaspectsoftheevolutionarytreefromobtainableinformationaboutthespecies,e.g.genomicdata,isawidelystudiedproblemseeGus eld(1997),Chapter17.Manymethodsareonlyconcernedwithestimatingtheundirectedtreetopologyinducedbyignoringthelocationoftherootandthelengthoftheedges,usuallyunderthefurtherassumptionthatallinternalnodeshavedegree3.Fortheremainderofthispaper,anevolutionarytreedenotessuchanunrootedevolutionarytreeofdegree3.
Differentmethodsusuallyyielddifferentevolutionarytreesforthesamesetofspecies,andthesamemethodcanyielddifferentevolutionarytreesforthesamesetofspecieswhenappliedtodifferentinformationaboutthespecies,e.g.differ-entgenes.Tostudysuchdifferencesinasystematicmanner,onemustbeabletoquantifydifferencesbetweentreesbywell-de nedandef cientmethods.
Oneapproachistocomputethedistancebetweentwotreesbasedonawell-de neddistancemeasure.Severaldistancemeasureshavebeenproposed,eachwithdifferentproperties
To
ALGORITHM
Thealgorithmcountsthenumberofquartettopologydiffer-encesbetweentwotreesT1andT2ofnspeciesbycountingthenumberofsharedquartets n inT1andT2andsubtractingthisfromthetotalnumberof4possiblequartets.Tocountsharedquartets,thealgorithmassociatesaquartetab|cdtotheuniquenodeinT1wherethepathsfromaandbtocjoin.Inarecurs-ivetraversalofT1,itcountsforeachinternalnodeinT1thenumberofassociatedquartetsthatarealsoquartetsinT2.Toimplementthecountingef ciently,thealgorithmemploysadatastructurewherethemainpartisahierarchicaldecompos-itionofT2.ThisisarootedbinarytreewithheightO(logn).Eachnodeinthehierarchicaldecompositionstoresatripletofintegersandapolynomialofatmostninevariableswithtotaldegreeatmost4.Countingisperformedbymanipulationofthepolynomialsalongleaf-to-rootpaths[seeBrodaletal.(2001)fordetails].
3IMPLEMENTATION
whomcorrespondenceshouldbeaddressed.
QDistisanimplementationoftheabovealgorithminC++thatshouldcompileonanyplatformsupportingautoconf,makeandgcc.IthasbeentestedonvariousversionsofLinux,Solaris,IRIXandOSX.Theprogramqdisttakesasinputtwotrees(overthesamesetofspecies)inNewickformatandoutputsthequartetdistancebetweentheminaformatdeterm-inedbythe--verboseoption.Usethe--helpoptionformoreinformation.
OurinitialimplementationofQDistfollowedcloselythedescriptioninBrodaletal.(2001).Pro lingshowed,assus-pected,thatmostoftherunningtimewasspentmanipulating
1636
Bioinformatics20(10)©OxfordUniversityPress2004;allrightsreserved.
Summary QDist is a progr... 暂无评价 2页 ... 1995) and the quartet-mapping approach for ...address: School of Computing Science, University ...
The Intractability of Co... 暂无评价 15页 免费 Computing the quartet di... [summary by Pierre Nicod`eme] We compute lower bounds for the distance ...
Summary: We have developed a tool implementing ...The ?rst algorithm for computing the re?ned ... (unweighted) quartet methods and neighbor-joining...
The Intractability of Co... 暂无评价 15页 免费 Computing the quartet di... [summary by Pierre Nicod`eme] We compute lower bounds for the distance ...
热门文档