文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Summary QDist is a program for computing the quartet
侵权投诉

Summary QDist is a program for computing the quartet

Summary QDist is a program for computing the quartet

BIOINFORMATICSAPPLICATIONSNOTE

Vol.20no.102004,pages1636–1637

Summary QDist is a program for computing the quartet

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.

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email