applied mathematics.

《applied mathematics.》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ThePerformanceofPhylogeneticMethodsonTreesofBoundedDiameterLuayNakhleh1,UsmanRoshan1,KatherineSt.John12,JerrySun1,andTandyWarnow131DepartmentofComputerSciences,UniversityofTexas,Austin,TX78712;
    !#"$

2、%#"&2DepartmentofMath&ComputerScience,LehmanCollege&theGraduateCenter,CityUniversityofNewYorkSupportedinpartbyNSFAward99-73874andtheTexasInstituteforComputationalandAppliedMathematics.3SupportedbytheDavidandLucilePackardFoundation.Abstract.Westudytheconvergence

3、rateofneighborjoiningandseveralnewphylogeneticreconstructionmethodsonfamiliesoftreesofboundeddiameter.Ourstudypresentstheoreticallyobtainedconvergencerates,aswellasanem-piricalstudybaseduponsimulationofevolutiondownrandombirthdeathtreesand“biological”modeltrees.Wefindthat

4、thenewphylogeneticmethodsofferanadvantageovertheNJmethod,exceptforlowratesofevolution,wheretheyhavecomparableperformance.TheimprovementinperformanceofthenewmethodsoverNJincreasewiththenumberoftaxaandtherateofevolution.1IntroductionPhylogenetictrees(thatis,evolutionarytre

5、es)formanimportantpartofmuchbiologicalresearch.Therearemanyalgorithmsforinferringphylogenetictrees.Themajorityofthesemethodsaredesignedtobeusedonbiomolecular(i.e.DNA,RNA,oramino-acid)sequences.Methodsforinferringphylogeniesfrombiomolec-ularsequencedataarestudied(boththeo

6、reticallyandempirically)withrespecttothetopologicalaccuracyoftheinferredtrees.Suchstudiesevaluatetheeffectsofvariousmodelconditions(suchasthesequencelength,theratesofevolutiononthetree,andthetree“shape”)ontheperformanceofvariousmethods.Thesequencelengthrequirementofameth

7、odisthesequencelengthneededbythemethodinordertoobtain(withhighprobability)thetruetreetopology.Earlierstudiesestablishedanalyticalupperboundsonthesequencelengthre-quirementsofvariousmethods(includingthepopularNeighborJoining[14])method.Thesestudiesshowedthatstandardmethod

8、s,suchasneighborjoining,recoverthetruetree(withhighprobability)fromsequencesoflengthsthatareexponential