Detection and validation of single gene inversions.

MOTIVATION: The biologically meaningful algorithmic study of genome rearrangement should take into account the distribution of sizes of the rearranged genomic fragments. In particular, it is important to know the prevalence of short inversions in order to understand the patterns of gene order disruption observed in comparative genomics. RESULTS: We find a large excess of short inversions, especially those involving a single gene, in comparison with a random inversion model. This is demonstrated through comparison of four pairs of bacterial genomes, using a specially-designed implementation of the Hannenhalli-Pevzner theory, and validated through experimentation on pairs of random genomes matched to the real pairs.

Gene and genome duplication.

Genomic sequencing projects have revealed the productivity of processes duplicating genes or entire chromosome segments. Substantial proportions of the yeast, Arabidopsis and human gene complements are made up of duplicates. This has prompted much interest in the processes of duplication, functional divergence and loss of genes, has renewed the debate on whether an early vertebrate genome was tetraploid, and has inspired mathematical models and algorithms in computational biology.

Early eukaryote evolution based on mitochondrial gene order breakpoints.

The comparison of the gene orders in a set of genomes can be used to infer their phylogenetic relationships and to reconstruct ancestral gene orders. For three genomes this is done by solving the "median problem for breakpoints"; this solution can then be incorporated into a routine for estimating optimal gene orders for all the ancestral genomes in a fixed phylogeny. For the difficult (and most prevalent) case where the genomes contain partially different sets of genes, we present a general heuristic for the median problem for induced breakpoints. A fixed-phylogeny optimization based on this is applied in a phylogenetic study of a set of completely sequenced protist mitochondrial genomes, confirming some of the recent sequence-based groupings which have been proposed and, conversely, confirming the usefulness of the breakpoint method as a phylogenetic tool even for small genomes.

Phylogenetic invariants for genome rearrangements.

We review the combinatorial optimization problems in calculating edit distances between genomes and phylogenetic inference based on minimizing gene order changes. With a view to avoiding the computational cost and the "long branches attract" artifact of some tree-building methods, we explore the probabilization of genome rearrangement models prior to developing a methodology based on branch-length invariants. We characterize probabilistically the evolution of the structure of the gene adjacency set for reversals on unsigned circular genomes and, using a nontrivial recurrence relation, reversals on signed genomes. Concepts from the theory of invariants developed for the phylogenetics of homologous gene sequences can be used to derive a complete set of linear invariants for unsigned reversals, as well as for a mixed rearrangement model for signed genomes, though not for pure transposition or pure signed reversal models. The invariants are based on an extended Jukes-Cantor semigroup. We illustrate the use of these invariants to relate mitochondrial genomes from a number of invertebrate animals.

Gene order breakpoint evidence in animal mitochondrial phylogeny.

Multiple genome rearrangement methodology facilitates the inference of animal phylogeny from gene orders on the mitochondrial genome. The breakpoint distance is preferable to other, highly correlated but computationally more difficult, genomic distances when applied to these data. A number of theories of metazoan evolution are compared to phylogenies reconstructed by ancestral genome optimization, using a minimal total breakpoints criterion. The notion of unambiguously reconstructed segments is introduced as a way of extracting the invariant aspects of multiple solutions for a given ancestral genome; this enables a detailed reconstruction of the evolution of non-tRNA mitochondrial gene order.

Genome rearrangement with gene families.

MOTIVATION: The theory and practice of genome rearrangement analysis breaks down in the biologically widespread contexts where each gene may be present in a number of copies, not necessarily contiguous. In some of these contexts it is, however, appropriate to ask which members of each gene family in two genomes G and H, lengths lG and lH, are its true exemplars, i.e. which best reflect the original position of the ancestral gene in the common ancestor genome. This entails a search for the two exemplar strings of same length n (= number of gene families, including singletons), having the smallest possible rearrangement distance: the exemplar distance. RESULTS: A branch and bound algorithm calculates these distances efficiently when based on easily calculated traditional rearrangement distances, such as signed reversals distance or breakpoint distance, which also satisfy a property of monotonicity in the number of genes. Simulations show that in two random genomes, the expected exemplar distance/n is sensitive to the number and size of gene families, but approaches 1 as the number of singleton families increases. When the basic rearrangement distance is just the number of breakpoints, the expected cost of computing the exemplar breakpoints distance (EBD), as measured by total calls to the underlying breakpoint distance routine, is highly dependent on both n and the configuration of gene families. On the other hand, basing exemplar distance on exemplar reversals distance (ERD), the expected computing cost depends on the configuration of gene families but is not sensitive to n. AVAILABILITY: Code for EBD and ERD is available from the author or may be accessed at http://www.crm.umontreal.ca/viart/exemplar_di s. html CONTACT: sankoff@ere.umontreal.ca.

On the Reconstruction of Ancient Doubled Circular Genomes Using Minimum Reversals.

We propose a model of the doubling of a bacterial genome followed by gene order rearrangement to explain present-day patterns of duplicated genes. On the hypothesis that inversion (reversal) is the predominant mechanism of rearrangement, we ask how to reconstruct the ancestral genome at the moment of genome duplication. We present a polynomial algorithm for finding such a genome that minimizes (within 2 reversals) the Hannenhalli-Pevzner formula for reversal distance from the modern genome. We illustrate by applying the algorithm to a set of duplicate genes in the Marchantia polymorpha mitochondrial genome.

Counting on comparative maps.

Comparative maps record the history of chromosome rearrangements that have occurred during the evolution of plants and animals. Effective use of these maps in genetic and evolutionary studies relies on quantitative analyses of the patterns of segment conservation. We review the analytical methods that have been developed for characterizing these maps and evaluate their application to existing comparative maps mainly for plants and animals.

Multiple genome rearrangement and breakpoint phylogeny.

Multiple alignment of macromolecular sequences generalizes from N = 2 to N > or = 3 the comparison of N sequences which have diverged through the local processes of insertion, deletion and substitution. Gene-order sequences diverge through non-local genome rearrangement processes such as inversion (or reversal) and transposition. In this paper we show which formulations of multiple alignment have counterparts in multiple rearrangement. Based on difficulties inherent in rearrangement edit-distance calculation and interpretation, we argue for the simpler "breakpoint analysis." Consensus-based multiple rearrangement of N > or = 3 orders can be solved exactly through reduction to instances of the Travelling Salesman Problem (TSP). We propose a branch-and-bound solution to TSP particularly suited to these instances. Simulations show how non-uniqueness of the solution is attenuated with increasing numbers of data genomes. Tree-based multiple alignment can be achieved to a great degree of accuracy by decomposing the tree into a number of overlapping 3-stars centered on the non-terminal nodes, and solving the consensus-based problem iteratively for these nodes until convergence. Accuracy improves with very careful initializations at the non-terminal nodes. The degree of non-uniqueness of solutions depends on the position of the node in the tree in terms of path length to the terminal vertices.

Genome structure and gene content in protist mitochondrial DNAs.

Although the collection of completely sequenced mitochondrial genomes is expanding rapidly, only recently has a phylogenetically broad representation of mtDNA sequences from protists (mostly unicellular eukaryotes) become available. This review surveys the 23 complete protist mtDNA sequences that have been determined to date, commenting on such aspects as mitochondrial genome structure, gene content, ribosomal RNA, introns, transfer RNAs and the genetic code and phylogenetic implications. We also illustrate the utility of a comparative genomics approach to gene identification by providing evidence that orfB in plant and protist mtDNAs is the homolog of atp8 , the gene in animal and fungal mtDNA that encodes subunit 8 of the F0portion of mitochondrial ATP synthase. Although several protist mtDNAs, like those of animals and most fungi, are seen to be highly derived, others appear to be have retained a number of features of the ancestral, proto-mitochondrial genome. Some of these ancestral features are also shared with plant mtDNA, although the latter have evidently expanded considerably in size, if not in gene content, in the course of evolution. Comparative analysis of protist mtDNAs is providing a new perspective on mtDNA evolution: how the original mitochondrial genome was organized, what genes it contained, and in what ways it must have changed in different eukaryotic phyla.

Phylogenetic Invariants for Metazoan Mitochondrial Genome Evolution.

The method of phylogenetic invariants was developed to apply to aligned sequence data generated, according to a stochastic substitution model, for N species related through an unknown phylogenetic tree. The invariants are functions of the probabilities of the observable N-tuples, which are identically zero, over all choices of branch length, for some trees. Evaluating the invariants associated with all possible trees, using observed N-tuple frequencies over all sequence positions, enables us to rapidly infer the generating tree. An aspect of evolution at the genomic level much studied recently is the rearrangements of gene order along the chromosome from one species to another. Instead of the substitutions responsible for sequence evolution, we examine the non-local processes responsible for genome rearrangements such as inversion of arbitrarily long segments of chromosomes. By treating the potential adjacency of each possible pair of genes as a position", an appropriate substitution" model can be recognized as governing the rearrangement process, and a probabilistically principled phylogenetic inference can be set up. We calculate the invariants for this process for N=5, and apply them to mitochondrial genome data from coelomate metazoans, showing how they resolve key aspects of branching order.

Synteny conservation and chromosome rearrangements during mammalian evolution.

An important problem in comparative genome analysis has been defining reliable measures of synteny conservation. The published analytical measures of synteny conservation have limitations. Nonindependence of comparisons, conserved and disrupted syntenies that are as yet unidentified, and redundant rearrangements lead to systematic errors that tend to overestimate the degree of conservation. We recently derived methods to estimate the total number of conserved syntenies within the genome, counting both those that have already been described and those that remain to be discovered. With this method, we show that approximately 65% of the conserved syntenies have already been identified for humans and mice, that rates of synteny disruption vary approximately 25-fold among mammalian lineages, and that despite strong selection against reciprocal translocations, inter-chromosome rearrangements occurred approximately fourfold more often than inversions and other intra-chromosome rearrangements, at least for lineages leading to humans and mice.

An ancestral mitochondrial DNA resembling a eubacterial genome in miniature.

Mitochondria, organelles specialized in energy conservation reactions in eukaryotic cells, have evolved from eubacteria-like endosymbionts whose closest known relatives are the rickettsial group of alpha-proteobacteria. Because characterized mitochondrial genomes vary markedly in structure, it has been impossible to infer from them the initial form of the proto-mitochondrial genome. This would require the identification of minimally derived mitochondrial DNAs that better reflect the ancestral state. Here we describe such a primitive mitochondrial genome, in the freshwater protozoon Reclinomonas americana. This protist displays ultrastructural characteristics that ally it with the retortamonads, a protozoan group that lacks mitochondria. R. americana mtDNA (69,034 base pairs) contains the largest collection of genes (97) so far identified in any mtDNA, including genes for 5S ribosomal RNA, the RNA component of RNase P, and at least 18 proteins not previously known to be encoded in mitochondria. Most surprising are four genes specifying a multisubunit, eubacterial-type RNA polymerase. Features of gene content together with eubacterial characteristics of genome organization and expression not found before in mitochondrial genomes indicate that R. americana mtDNA more closely resembles the ancestral proto-mitochondrial genome than any other mtDNA investigated to date.

Conserved segment identification.

The quantitative study of evolution based on comparative map data is dependent on the definition and identification of conserved segments remaining after interchromosomal exchanges such as reciprocal translocation. Because of experimental error and, more important, extensive local intrachromosomal rearrangement, it is difficult to reconstruct the configuration of conserved segments produced by interchromosomal exchanges. We present a formula to evaluate possible conserved segments and an algorithm which seeks the partition of the genome into segments optimal under this evaluation. Application is made to the human-mouse comparison.

Breakpoint Phylogenies.

We describe a number of heuristicsfor inferring the gene orders of the hypothetical ancestral genomes in a fixed phylogeny. The optimization criterion is the minimum number of breakpoints (pairs of genes adjacent in one genome but not the other) in the gene orders of two genomes connected by an edge of the tree, summed over all edges. The key to the method is an exact solution for trees with three leaves (the median problem) based on a reduction to the Traveling Salesman Problem.

Comparable rates of gene loss and functional divergence after genome duplications early in vertebrate evolution.

Duplicated genes are an important source of new protein functions and novel developmental and physiological pathways. Whereas most models for fate of duplicated genes show that they tend to be rapidly lost, models for pathway evolution suggest that many duplicated genes rapidly acquire novel functions. Little empirical evidence is available, however, for the relative rates of gene loss vs. divergence to help resolve these contradictory expectations. Gene families resulting from genome duplications provide an opportunity to address this apparent contradiction. With genome duplication, the number of duplicated genes in a gene family is at most 2n, where n is the number of duplications. The size of each gene family, e.g., 1, 2, 3, ..., 2n, reflects the patterns of gene loss vs. functional divergence after duplication. We focused on gene families in humans and mice that arose from genome duplications in early vertebrate evolution and we analyzed the frequency distribution of gene family size, i.e., the number of families with two, three or four members. All the models that we evaluated showed that duplicated genes are almost as likely to acquire a new and essential function as to be lost through acquisition of mutations that compromise protein function. An explanation for the unexpectedly high rate of functional divergence is that duplication allows genes to accumulate more neutral than disadvantageous mutations, thereby providing more opportunities to acquire diversified functions and pathways.