Combinatorial Problems in Genome Rearrangements

University Of California-San Diego, La Jolla CA

Investigators

Abstract

Molecular evolution studies are usually based on analysis of sequence variations in individual genes, rather than whole genomes. However, evolutionary trees for different genes may lead to different results. An alternative approach is to study the evolutionary history of whole genomes rather than individual genes, based on comparison of the order of homologous genes (or segments) between genomes. This approach is known as genome rearrangements. Genome rearrangements may be used to study the evolutionary process that led from unknown ancestral genomes to present day genomes, and to study the possible architectures of the ancestral genomes. This project will use combinatorial techniques to study genome rearrangements. The "breakpoint graph" is a combinatorial graph developed to compare gene orders in two different genomes. There are well-developed techniques for studying genome rearrangements between two genomes based on the cycle structure of the breakpoint graph. Although a generalization of the definition of breakpoint graphs to multiple genomes is straightforward, methods to analyze this graph do not so easily generalize. Most studies of multiple genomes that use breakpoint graphs do two genomes at a time with ordinary breakpoint graphs, and combine the pairwise results. This project will develop ways to use the multiple genome breakpoint graph more effectively. There are several related applications: the construction of phylogenetic trees based on genome rearrangements; the study of potential ancestral gene orders; and the study of "breakpoint reuse," which is the apparent or actual multiple use of a breakpoint region in a series of genome rearrangements. Another mathematical construct used to represent different gene orders is permutations. This project will also generalize classical work on permutation enumeration to the context of genome rearrangements with multiple genomes and multiple chromosomes. Chromosomal evolution has long been of interest to biologists, and has recently caught the interest of mathematicians and computer scientists. This interest has been greatly accelerated by the Human Genome Project and similar projects to sequence the genomes of other species. These projects are national priorities, largely funded in the U.S. by the National Human Genome Research Institute and the Department of Energy. Sequences or maps of different genomes are compared to find the corresponding genes and other features. Many studies are focused on variations of the sequences within corresponding genes. However, it is also of interest that the corresponding genes have usually moved to different chromosomes, moved into a different order within the same chromosome, or have been duplicated or deleted. Additionally, chromosomes may be broken into two or fused together into one. These phenomena are known as genome rearrangements, and the mathematical techniques and computer algorithms for studying complicated genome rearrangements have largely been developed only since the 1990s. This project is focused on the use of particular mathematical techniques to study genome rearrangements and evolutionary trees.