Gene team tree: A compact representation of all gene teams

Abstract

The identification of conserved gene clusters is an important step towards understanding genome evolution and predicting the function of genes. Gene team is a model for conserved gene clusters that takes into account the position of genes on a genome. Existing algorithms for finding gene teams require the user to specify the maximum distance between adjacent genes in a team. However, determining suitable values for this parameter, δ, is non-trivial. Instead of trying to determine a single best value, we propose constructing the gene team tree (GTT), which is a compact representation of all gene teams for every possible value of δ. Our algorithm for computing the GTT extends existing gene team mining algorithms without increasing their time complexity. We compute the GTT for E. coli K-12 and B. subtilis and show that E. coli K-12 operons are recovered at different values of δ. We also describe how to compute the GTT for multi-chromosomal genomes and illustrate using the GTT for the human and mouse genomes. © 2008 Springer-Verlag.