PhyloLab Whole Genome Page

---

---

Phylogeny Reconstruction from Gene Order 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.  Many single-chromosome organisms and organelles have circular chromosomes. Given a particular strand from a single chromosome, whether linear or circular, we can infer the ordering of the genes, along with directionality of the genes, thus representing each chromosome by an ordering (linear or circular) of signed genes. Note that picking the complementary strand produces a different ordering, in which the genes appear in the reverse direction and reverse order. The evolutionary process that operates on the chromosome can thus be seen as a transformation of signed orderings of genes.

People

Faculty

• Tandy Warnow,  Department of Computer Sciences, UT-Austin
• Robert Jansen,  Section of Integrative Biology, School of Biological Sciences, UT-Austin
• Linda Raubeson, Reed College, Portland, OR
• Bernard Moret, EPFL, Switzerland
• David Bader,  Department of Electrical and Computer Engineering, University of New Mexico, Albuquerque

• Li-San Wang, Ph.d student, Department of Computer Sciences, UT-Austin

Software

• GRAPPA: Genome Rearrangement Analysis under Parsimony and other Phylogenetic Algorithms        download the software

Publications

• Moret, B.M.E., Wang, L.-S., Warnow, T., and Wyman, S., ``New approaches for reconstructing phylogenies based on gene order,'' submitted to 9th Int'l Conf. on Intelligent Systems for Molecular Biology ISMB-2001 ps or pdf.
• Moret, B.M.E., Bader, D.A., and Warnow, T., ``High-performance algorithm engineering in computational phylogeny,'' Proc. Int'l Conf. Computational Science 2001 (invited)
• Bader, D.A., Moret, B.M.E., Warnow, T., Wyman, S.K., and Yan, M., ``High-performance algorithm engineering for gene-order phylogenies,'' DIMACS Workshop on Whole Genome Comparison, Rutgers U., 2001. ps or pdf.
• Moret, B.M.E., Wyman, S., Bader, D.A., Warnow, T., and Yan, M., ``A detailed study of breakpoint analysis,'' Proc. 6th Pacific Symp. Biocomputing PSB 2001, Hawaii, World Scientific Pub. (2001), 583--594. ps or pdf.
• Cosner, M.E., Jansen, R.K., Moret, B.M.E., Raubeson, L.A., Wang, L.S., Warnow, T., and Wyman, S., ``An empirical comparison of phylogenetic methods on chloroplast gene order data in Campanulaceae,'' Proc. Gene Order Dynamics, Comparative Maps, and Multigene Families DCAF-2000, Montreal (2000), in Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment, and the Evolution of Gene Families, D. Sankoff and J. Nadeau, eds., Kluwer Academic, Dordrecht (2000), 99--121. ps or pdf.
• Cosner, M.E., Jansen, R.K., Moret, B.M.E., Raubeson, L.A., Wang, L.S., Warnow, T., and Wyman, S., ``A new fast heuristic for computing the breakpoint phylogeny and a phylogenetic analysis of a group of highly rearranged chloroplast genomes,'' Proc. 8th Int'l Conf. on Intelligent Systems for Molecular Biology ISMB-2000, San Diego (2000), 104--115. ps or pdf.
• Li-San Wang and Tandy Warnow,``Estimating true evolutionary distances between genomes,'' To appear in the Proceedings of the Thirty-Third Annual ACM Symposium on the Theory of Computing (STOC'01), Crete, Greece (2001). ps or pdf
• Li-San Wang and Tandy Warnow, ``New polynomial time methods for whole genome phylogeny reconstruction,'' presented at the DIMACS Whole Genome Comparison Workshop, Piscataway, NJ, Feb. 28 - Mar. 2 (2001).