An Approximation Algorithm for Character Compatibility and Fast Quartet-based Phylogenetic Tree Comparison

Computer Science;phylogenetic analysis;phylogeny reconstruction;combinatorial algorithms;algorithm analysis;bioinformatics

Tsang, John

University of Waterloo

关键词: Computer Science;    phylogenetic analysis;    phylogeny reconstruction;    combinatorial algorithms;    algorithm analysis;    bioinformatics;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/1110/1/jsctsang2000.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Phylogenetic analysis, or the inference of evolutionary historyisdone routinely by biologists and is one of themost important problems in systematic biology.In this thesis, we study two computational problems in the area. First, we study the evolutionary tree reconstructionproblemunder the character compatibility(CC) paradigm and give a polynomial time approximationscheme(PTAS)foravariation of the formulationcalledfractional character compatibility (FCC),whichhasbeen proven to be NP-hard.We also presentaverysimplealgorithmcalled the Ordinal SplitMethod(OSM)togeneratebipartitionsgiven sequencedata,whichcan be served as a front-end to thePTAS.The performance of the OSM and the validity oftheFCC formulation are studied through simulation experiments. Thesecondpartof this thesis presents an efficient algorithmtocompareevolutionarytreesusingthe quartet metric. Differentevolutionaryhypothesis ariseswhendifferentdatasetsareusedor when differenttreeinferencemethodsare applied to the samedata set.Tree comparisons are routinely done by biologiststoevaluatethequalityoftheirtree inferenceexperiments. Thequartetmetric has many desirablepropertiesbut its use has been hindered by itsrelativelyheavycomputational requirements.We addressthisproblemby giving the first O(n^2) time algorithmtocompute the quartet distance between two evolutionary trees.