Abstract
An important model of a conserved gene cluster is called the gene team model, in which a chromosome is defined to be a permutation of distinct genes and a gene team is defined to be a set of genes that appear in two or more species, with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold δ. A gene team tree is a succinct way to represent all gene teams for every possible value of δ. The previous fastest algorithm for constructing a gene team tree of two chromosomes requires O(n lg n lg lg n time, which was given by Wang and Lin. Its bottleneck is a problem called the maximum-gap problem. In this paper, by presenting an improved algorithm for the maximum-gap problem, we reduce the upper bound of the gene team tree problem to O(n lg nα (n)). Since α grows extremely slowly, this result is almost as efficient as the current best upper bound, O(n lg n)$, for finding the gene teams of a fixed δ value. Our new algorithm is very efficient from both the theoretical and practical points of view. Wang and Lin's gene-team-tree algorithm can be extended to k chromosomes with complexity O(kn lg n lg lg n). Similarly, our improved algorithm for the maximum-gap problem reduces this running time to O(kn lg nα (n)). In addition, it also provides new upper bounds for the gene team tree problem on general sequences, in which multiple copies of the same gene are allowed. © 2004-2012 IEEE.