Algorithms Research (Tandy Warnow, Focus Leader)

1. Solving hard optimization problems on huge datasets
   Current approaches for phylogenetic reconstruction generally attempt to solve hard optimization problems such as maximum parsimony and maximum likelihood. Current techniques do not seem able to provide good analyses on datasets containing thousands of sequences in reasonable time periods. Finding new approaches which can enable new techniques to scale to datasets containing tens of thousands of sequences is the focus of the algorithms research for CIPRES. Our current techniques employ divide-and-conquer strategies to work with existing "base methods" and are able to speed up standard software by at least one order of magnitude. Contact Tandy Warnow for more information.
   

2. The analytical study of convergence rates of different methods, and the development of provably fast-converging methods
   Absolute fast converging phylogenetic reconstruction methods are provably guaranteed to recover the true tree with high probability from sequences that grow only polynomially in the number of leaves, once the edge lengths are bounded arbitrarily from above and below. Only a few methods have been determined to be absolute fast converging; these have all been developed in just the last few years, and most are polynomial time. Our new methods outperform both neighbor joining and the previous fast converging methods, returning very accurate large trees, when these other methods do poorly. Contact Tandy Warnow for more information.
   

3. The inference of phylogenetic trees from gene order and content data
   The genomes of some organisms have a single chromosome or contain single-chromosome organelles (such as mitochondria or chloroplasts) whose evolution is largely independent of the evolution of the nuclear genome for these organisms. Evolutionary processes, such as inversions and transpositions, scramble the gene order without changing the gene content; other processes, such as duplications, insertions, and deletions, change the gene content as well. Because these events happen less frequently than site substitutions, it is possible to infer deep evolutionary histories with greater accuracy from gene order and content data. This project is developing software for performing whole genome phylogenetic reconstructions, for single chromosome genomes. See the GRAPPA web page for more on this project or contact Bernard Moret.
   

4. Visualization of large trees, and clustering of sets of phylogenetic trees
   Visualizing a single large tree containing thousands of leaves is currently beyond the reach of any software package. In this project, we are developing software to make such visualizations attractive and flexible. We are also developing visualization software for examining the output of a phylogenetic analysis containing many (hundreds or thousands) of different phylogenies. See the web pages of Nina Amenta and Tamara Munzner for more on this project.
   

5. Phylogenetic Networks
   Phylogenies, i.e., the evolutionary histories of groups of organisms, play a major role in representing the interrelationships among biological entities. Many methods for reconstructing such phylogenies have been proposed, but almost all of them assume that the underlying evolutionary history of a given set of species can be represented by a tree. While this model gives a satisfactory first-order approximation for many families of organisms, other families exhibit evolutionary mechanisms that cannot be represented by a tree. Processes such as hybridization and horizontal gene transfer result in networks of relationships rather than trees of relationships. Although this problem is widely appreciated, there has been comparatively little work on computational methods for estimating evolutionary networks. Currently, we are working on developing the methodologies, algorithms, and tools reconstructing phylogenetinc networks in the presence of hybridization and horizontal gene transfer. We are also developing simulations tools and distance metrics for phylogenenetic networks. Contact Randy Linder and Luay Nakhleh for more information on this project.
   

6. Post-processing sets of phylogenetic trees
   For a variety of reasons, a typical outcome of a phylogenetic analysis of a dataset can consist of many different unrooted trees, and each tree represents an equally believable estimate of the true tree. Making sense of the set of these trees is then a challenging prospect. Consensus tree techniques such as "strict consensus" and "majority consensus" are the most popular, although methods (such as the maximum agreement subtree) based upon eliminating taxa in order to obtain better solutions are also of interest. Our research in this project is developing alternative techniques for consensus and agreement methods. Contact Tandy Warnow for more information.

For more information, see the Phylo Lab at the University of Texas at Austin

CIPRES is a Collaboration of the Following Institutions:
American Museum of Natural History, Florida State University, New Jersey Institute of Technology, North Carolina State University, Rice University, San Diego Supercomputer Center, Texas A&M, University of Arizona, University of British Columbia, University of California at Berkeley, University of California at San Diego, University of Connecticut, University of Pennsylvania, Univ. of South Carolina, University of Texas at Austin, and Yale University. xhtml | css