Simultaneous Gene Finding in Several Aligned Genomes

Many sequenced genomes are so closely related to other sequenced genomes that most of their coding regions can be aligned, for example the nearly 50 new bird genomes. Experimental evidence or a trustable annotation exists for some subset of all loci of all genomes. A multiple alignment of genomes can be used to transfer evidence across species and also provides strong evolutionary evidence through negative selection and sequence conservation.

We address the simultaneous identification of the structure of all genes in all aligned genomes, thereby respecting structural differences but exploiting synteny, conservation and negative selection. We formulate the comparative gene prediction problem as a discrete optimization problem on a graph. The nodes of the graph represent candidate exons of each of the genomes and also of ancestral genomes. The joint gene structure is represented by a set of paths in the graph, one path for each genome. Joint gene structures are scored as in single-species gene-finders using sequence-intrinsic statistical and extrinsic evidence where available. In addition, aligned exon candidates are phylogenetically scored using an estimate of the ratio of nonsynonymous versus synonymous substitutions and conservation of sequence and signals. This approach differs from previous comparative gene prediction models which model only the structure of a single (NSCAN, CONTRAST) or two genomes (pair-HMMs) at a time. The gene-finder AUGUSTUS now implements a comparative gene finding option using an efficient approximation algorithm with guaranteed error bounds.