Parallel implementation of maximum parsimony search algorithm on multicore CPUs

Show simple item record

dc.contributor.advisor Skuse, Gary
dc.contributor.advisor Khanna, Gurcharan
dc.contributor.advisor Kaminsky, Alan
dc.contributor.author Darling, Andrew
dc.date.accessioned 2012-01-16T16:43:01Z
dc.date.available 2012-01-16T16:43:01Z
dc.date.issued 2011-11
dc.identifier.uri http://hdl.handle.net/1850/14570
dc.description.abstract Phylogenetics is the study of the evolutionary relationships among species. It is derived from the ancient greek words, phylon meaning "race", and genetikos, meaning "relative to birth". An important methodology in phylogenetics is a cladistics methodology (parsimony) applied to the study of taxonomic classification. Modern study includes as source data aspects of molecular biology, such as the DNA sequence of homologous (orthologous) genes. The algorithms used attempt to reconstruct evolutionary relationships in the form of phylogenetic trees, based on the available morphological data, behavioral data, and usually DNA sequence data (Fitch W. M., 1971). The topic of this thesis is the parallel implementation of an existing algorithm called Maximum Parsimony, a search for a guaranteed optimal tree(s) based the fewest number of mutations required for tree construction. The algorithm grows linearly with the increase in DNA sequence length and combinatorially with the number of organisms studied (Felsenstein J. , The number of evolutionary trees., 1978). The algorithm may take hours to complete. The limitations of the current implementations such as PAUP are that they are limited to just one core on the CPU, even if 8 are available. This parallel implementation may use as many cores as are available. The method of research is to replicate the accuracy of existing serial software, parallelize the algorithm to many cores without losing accuracy, optimize by various methods, then attempt to port to other hardware architectures. Some time is spent on the implementation of the algorithms onto GPUs and Clusters. The results are that, while this implementation matches the accuracy of the current standard, and speeds up in parallel, it does not presently match the speed of PAUP for reasons yet to be determined. en_US
dc.language.iso en_US en_US
dc.subject Maximum parsimony en_US
dc.subject Multicore CPUs en_US
dc.subject Parallel en_US
dc.subject.lcsh Cladistic analysis--Data processing en_US
dc.subject.lcsh Parallel algorithms en_US
dc.title Parallel implementation of maximum parsimony search algorithm on multicore CPUs en_US
dc.type Thesis en_US
dc.description.college College of Science en_US
dc.description.department School of Life Sciences en_US
dc.contributor.advisorChair Buckley, Larry

Files in this item

Files Size Format View
ADarlingThesis11-2011.pdf 1.116Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search RIT DML


Advanced Search

Browse