Rochester Institute of Technology
Parallelization of a Maximum Parsimony Branch and Bound Algorithm for Phylogenetic Inference
Abstract
dc:description.abstractPhyiogenetic inference involves the reconstruction of evolutionary relationships among species in the form of branching diagrams called trees. Specifically, certain biological structures common to all living organisms, such as morphological characteristics, protein sequences or DNA sequences can be compared Differences and similarities in these characteristics among species are used to reconstruct the evolutionary relationships and draw trees. Many methods of tree reconstruction are currently used. The method of maximum parsimony for phyiogenetic inference is a widely used algorithm which employs the hypothesis that the most likely tree for a given group of data will be the one which uses the least number of changes from an origin (root of the tree) to the terminal taxa The problems and corresponding solution algorithms associated with these searches are frequently implemented on single-processor systems, and can take weeks to complete for large data sets. Parallelization of these algorithms is therefore an important area of development in the bioinformatics community [1, 3, 17, 20, 25]. A free license, open-source, parallel implementation of a phyiogenetic inference program using maximum parsimony has yet to be developed, and it is the aim of this thesis to provide such a tool. It is hoped that the tool will work transparently with one of the most popular suites of free phyiogenetic inference tools called PHYLIP, developed by Joe Felsenstein at the University of Washington [7], by accepting and generating the same format of input and output data The tool would be a first step towards providing the academic community and others with improvements in performance and capabilities (through parallelization) over the currently available free distributions of phyiogenetic inference programs using parsimony, allowing for larger volumes of data to be analyzed in a reduced amount of time.
Degree
thesis:*- Name thesis:degree_name
- Computer Engineering (MS)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Computer Engineering (KGCOE)
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Howard, Curtis J.
- Contributors dc:contributor
-
- Muhammad Shaaban
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.rit.edu/theses/7986