|
|
The "holy grail" of biology is to understand the miracle of life, which can be studied through the myriad of species now living in our planet's seas, land, and sky. A key to this understanding is determining the "tree of life" (called a phylogeny), that represents the evolutionary process from the start of life itself to the present day species found all around us. In a phylogeny, known species are placed at the leaves of the tree, while ancestry (extinct) species are conjectured where branches split in the tree. This process is followed down to the base of the tree, normally represented by the three major limbs for plants, animals, and single-celled organisms.
During reproduction, species pass down genetic material (the instruction code for life) from parent(s) to offspring. In the last decade, techniques for determining these genetic sequences has been highly automated and several species now have their complete genomes known. However, finding the set of nucleotide sequences on each chromosome in a species is only the first task in understanding how life works. Next, genes, which are coding regions on the nucleotide sequence, must be found, and the protein functions from these genes must be understood.
In nature, many processes can change and alter the genetic material, for instance, sexual reproduction may combine information from both mother and father, or mistakes in translation can occur. For determining evolution, gene sequences in Mitochondrial DNA (for animals) and Chloroplasts (for plants) are often studied, since these typically mutate less frequently, and are often recorded on a circular strand of information. The evolutionary process typically contains changes where the circular band gets added genes ("insertion"), deleted genes ("deletion"), a portion twisted and re-attached in the same place ("inversion"), and portions snipped out but re-attached in a different location ("translocations"). Most of these changes are lethal, but occasionally a mutation causes the genesis of a new, related species.
These evolutionary models are approximations at best, but nevertheless, provide the best guidance for determining the interrelation of species. Often biologists are concerned with a small portion of the phylogeny (a subtree) containing a family of related species. It is thought that Nature follows a path of minimizing evolutionary processes, but even computing the minimum evolutionary tree (called "phylogeny reconstruction") for a handful of species is intractable on several levels.
Using the largest open, production Linux supercluster, LosLobos, researchers
at The University of New Mexico's Albuquerque High Performance Computing Center
(www.ahpcc.unm.edu) have achieved a nearly one-million-fold speedup in solving
the computationally-hard phylogeny reconstruction problem for the family of
twelve Bluebell
species (scientific name: Campanulacae) from the flowers' chloroplast gene order
data. (The problem size includes a thirteenth plant, Tobacco, used as a distantly-related
outgroup). Phylogenies derived from gene order data may prove crucial in answering
some fundamental open questions in biomolecular evolution. Yet very few techniques
are available for such phylogenetic reconstructions.
One method is breakpoint analysis, developed by Blanchette and Sankoff for solving the ``breakpoint phylogeny.'' Earlier experiments with various techniques for reconstructing phylogenies from gene order data suggested that Sankoff and Blanchette's implementation of BPAnalysis is much too slow. On a collection of Campanulaceae with 13 genomes of 105 gene segments, it is estimated that Sankoff and Blanchette's BPAnalysis would take well over 200 years to complete---an estimate based on the average number of trees processed by the code per unit time and extended to the 13,749,310,575 tree topologies on 13 leaves.
Professors David A. Bader (EECE, UNM) and Bernard M.E. Moret (Computer Science,
UNM) along with Professor Tandy Warnow (Computer Science, University of Texas
-- Austin) have solved the Campanulacae problem in about one hour and forty
minutes on the 512-processor UNM/Alliance LosLobos supercluster, an IBM Netfinity
cluster with 512 733MHz Pentium III processors, interconnected with four 64-way
Myrinet 2000 switches, and running the Linux 2.2 operating system. The parallelization
uses MPI and includes techniques for concurrently
evaluating candidate trees and sharing improved upper and lower bounds by the
processors.
The new phylogeny reconstruction code, GRAPPA, is freely available as open source from http://www.cs.unm.edu/~moret/GRAPPA/ and shows the power of algorithmic engineering techniques. Run on a single processor, GRAPPA performs 2500 times faster than the BPAnalysis code, using similar algorithms, but with the implementation paying close attention to the detail of cache-sensitive and efficient data structures and algorithms. GRAPPA is able to take full advantage of parallel computers like the LosLobos supercluster, for additional speedups. Hence, the total speedup for our solution (going from an estimated 200 years down to 100 minutes) is one million -- nearly 6 orders of magnitude.
This research is part of Moret and Bader's NSF Information Technology Research project "Algorithms for Irregular Discrete Computations on SMPs" based at the High Performance Computing, Educational and Research Center (HPCERC), a strategic center at The University of New Mexico.
*****************************************************************************
Using the largest open-production Linux supercluster in the world, LosLobos, researchers at The University of New Mexico's Albuquerque High Performance Computing Center (http://www.ahpcc.unm.edu) have achieved a nearly one-million-fold speedup in solving the computationally-hard phylogeny reconstruction problem for the family of twelve Bluebell species (scientific name: Campanulacae) from the flowers' chloroplast gene order data. (The problem size includes a thirteenth plant, Tobacco, used as a distantly-related outgroup). Phylogenies derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Yet very few techniques are available for such phylogenetic reconstructions.
One method is breakpoint analysis, developed by Blanchette and Sankoff for solving the ``breakpoint phylogeny.'' Earlier experiments with various techniques for reconstructing phylogenies from gene order data suggested that Sankoff and Blanchette's implementation of BPAnalysis is much too slow. On a collection of Campanulaceae with 13 genomes of 105 gene segments, it is estimated that Sankoff and Blanchette's BPAnalysis would take well over 200 years to complete---an estimate based on the average number of trees processed by the code per unit time and extended to the 13,749,310,575 tree topologies on 13 leaves.
Professors Bernard M.E. Moret (Computer Science, University fo New Mexico) and David A. Bader (Department of Electrical and Computer Engineering, University of New Mexico) along with Professor Tandy Warnow (Computer Science, University of Texas -- Austin) have solved the Campanulacae problem in about one hour and forty minutes on the 512-processor UNM/Alliance LosLobos supercluster, an IBM Netfinity cluster with 512 733MHz Pentium III processors, interconnected with four 64-way Myrinet 2000 switches, and running the Linux 2.2 operating system.
The new phylogeny reconstruction code, GRAPPA, is freely available as open source from http://www.cs.unm.edu/~moret/GRAPPA/ and shows the power of algorithmic engineering techniques. Run on a single processor, GRAPPA performs 2500 times faster than the BPAnalysis code, using similar algorithms, but with the implementation paying close attention to the detail of cache-sensitive and efficient data structures and algorithms. GRAPPA is able to take full advantage of parallel computers like the LosLobos supercluster, for additional speedups. Hence, the total speedup for our solution (going from an estimated 200 years down to 100 minutes) is one million -- nearly 6 orders of magnitude.
This research is part of Moret and Bader's NSF Information Technology Research project "Algorithms for Irregular Discrete Computations on SMPs" based at the High Performance Computing, Educational and Research Center (HPCERC), a strategic center at The University of New Mexico.
 |
|||||||
|
|||||||