Parallelizing the Phylogeny Problem

Jeff A. Jones

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-95-869
March 1995

http://www.eecs.berkeley.edu/Pubs/TechRpts/1995/CSD-95-869.pdf

The problem of determining the evolutionary history of species in the form of phylogenetic trees is known as the phylogeny problem. Drawing upon a technique known as character compatibility and an algorithm for a subproblem from Agarwala and Fernandez-Baca, modified according to a suggestion from Lawler, we present an algorithm and a proof of correctness. Based on experimental evidence, we have designed a highly-tuned sequential implementation. We also present an efficient parallel implementation based on a new distributed data structure.


BibTeX citation:

@techreport{Jones:CSD-95-869,
    Author = {Jones, Jeff A.},
    Title = {Parallelizing the Phylogeny Problem},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1995},
    Month = {Mar},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1995/5595.html},
    Number = {UCB/CSD-95-869},
    Abstract = {The problem of determining the evolutionary history of species in the form of phylogenetic trees is known as the phylogeny problem.  Drawing upon a technique known as character compatibility and an algorithm for a subproblem from Agarwala and Fernandez-Baca, modified according to a suggestion from Lawler, we present an algorithm and a proof of correctness.  Based on experimental evidence, we have designed a highly-tuned sequential implementation. We also present an efficient parallel implementation based on a new distributed data structure.}
}

EndNote citation:

%0 Report
%A Jones, Jeff A.
%T Parallelizing the Phylogeny Problem
%I EECS Department, University of California, Berkeley
%D 1995
%@ UCB/CSD-95-869
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1995/5595.html
%F Jones:CSD-95-869