Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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