Back to search

Rochester Institute of Technology

Parallelization of a Maximum Parsimony Branch and Bound Algorithm for Phylogenetic Inference

Abstract

dc:description.abstract

Phyiogenetic 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

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Howard, Curtis J.. Parallelization of a Maximum Parsimony Branch and Bound Algorithm for Phylogenetic Inference. Thesis thesis, https://repository.rit.edu/theses/7986