Algorithms and hypothesis selection in dynamic homology phylogenetic analysis
Item
-
Title
-
Algorithms and hypothesis selection in dynamic homology phylogenetic analysis
-
Identifier
-
d_2009_2013:a597e261bed2:10423
-
identifier
-
10547
-
Creator
-
Varon, Andres,
-
Contributor
-
Amotz Bar-Noy | Ward C. Wheeler
-
Date
-
2010
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer science | Bioinformatics | Generalized Tree Alignment | Kolmogorov Complexity | Phylogenetic Analysis | Tree Alignment
-
Abstract
-
Phylogeny and alignment estimation are two important, and closely related biological problems. In the typical alignment problem, insertions, deletions, and substitutions need to be inferred, to understand the evolutionary patterns of life. With the technological advances of the last 20 years, phylogenetic analyses will grow to include complete chromosomes and genomes. With these data sets, not only insertions, deletions, and substitutions, but also rearrangements such as duplications, translocations, transpositions, and inversions must be taken into consideration.;In this study, phylogenetic analysis is explored at three different levels. At the first level, new heuristic algorithms for the joint estimation of phylogenies and alignments under the Maximum Parsimony optimality criterion are described. Our experimental study showed that the new algorithms perform dramatically better when compared to previous heuristics. These new algorithms will allow biologists to analyze larger data sets in shorter periods of time. At the second level, new and existing algorithms where implemented in the computer program POY version 4. POY has had a significant impact in the biology community, and is used by hundreds of biologists around the world. POY will serve as a platform for long term research both in algorithm engineering, and biology. At the third level, the problem of parameter and model selection in complete chromosome analyses is explored. We propose and describe the use of Kolmogorov Complexity (KC) as optimality criterion, as a unifying criterion for phylogenetic analysis. Our evaluation using simulations showed that KC correctly identifies phylogeny and model with high frequency. These results are evidence that KC is very well suited for the difficulties posed by the phylogenetic analysis of complete genomes.
-
Type
-
dissertation
-
Source
-
2009_2013.csv
-
degree
-
Ph.D.
-
Program
-
Computer Science
