Dissertation/Thesis Abstract

A Static Formulation of the History Bound Problem
by Matsieva, Julia, M.S., University of California, Davis, 2014, 55; 1565692
Abstract (Summary)

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.

Indexing (document details)
Advisor: Gusfield, Daniel M.
Commitee: Green, Todd J., Su, Zhendong
School: University of California, Davis
Department: Computer Science
School Location: United States -- California
Source: MAI 53/06M(E), Masters Abstracts International
Subjects: Genetics, Mathematics, Bioinformatics, Computer science
Keywords: Phylogenetics
Publication Number: 1565692
ISBN: 978-1-321-21218-1
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy