Abstract
A gene team is a set of genes that appear in two or more species, possibly in a different order yet with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold. The focus of this paper is the problem of finding gene teams of two chromosomes. Béal et al. [1] had an O(nlog 2 n)-time algorithm for this problem. In this paper, two O(nlogd)-time algorithms are proposed, where d ≥ n is the number of gene teams. The proposed algorithms are obtained by modifying Béal et al.'s algorithm, using two different approaches. Béal et al.'s algorithm can be extended to find the gene teams of k chromosomes in O(knlog 2 n) time. Our improved algorithms can be extended to find the gene teams of k chromosomes in O(knlogd) time. © 2009 Springer Berlin Heidelberg.