Biologists working with DNA or character data are often interested in modeling the evolution of biological change present in their samples. The biological processes that create diversity are traditionally represented as branching events in the lineages of species. However, branching alone is insufficient to model all real-world data, hence there is an interest in constructing phylogenetic networks, or rooted DAGs, that simultaneously display multiple evolutionary trees or sometimes model biological processes, such as recombination. We often require that these networks fulfill an optimization criteria, such as having a minimum number of recombination or reticulation nodes.
In this work, we prove that the History Bound, a value previously computed as a lower bound on the minimum number of recombinations in a set of DNA data, is such an optimization criterion on phylogenetic networks; specifically, it is the minimum number of reticulation nodes in a particular type of network. This was stated earlier without a proof by other researchers. We also give an algorithm for constructing the network with this number of nodes and show that a network of this type with fewer reticulation nodes cannot exist.
|Advisor:||Gusfield, Daniel M.|
|Commitee:||Green, Todd J., Su, Zhendong|
|School:||University of California, Davis|
|School Location:||United States -- California|
|Source:||MAI 53/06M(E), Masters Abstracts International|
|Subjects:||Genetics, Mathematics, Bioinformatics, Computer science|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be