title: A New Efficient Algorithm for the Frequent Gene Team Problem.
abstract: The focus of this paper is the frequent gene team problem. Given a quorum parameter μ and a set of m genomes, the problem is to find gene teams that occur in at least μ of the given genomes. In this paper, a new algorithm is presented. Previous solutions are efficient only when μ is small. Unlike previous solutions, the presented algorithm does not rely on examining every combination of μ genomes. Its time complexity is independent of μ. Under some realistic assumptions, the practical running time is estimated to be , where n is the maximum length of the input genomes. Experiments showed that the presented algorithm is extremely efficient. For any μ, it takes less than 1 second to process 100 bacterial genomes and takes only 10 minutes to process 2,000 genomes. The presented algorithm can be used as an effective tool for large scale genome analyses.
authors.forename: Biing-Feng
authors.initials: BF
authors.lastname: Wang
mesh_terms: D000465:Algorithms; D016680:Genome, Bacterial / Q000235:genetics; D023281:Genomics / Q000379:methods*; D008957:Models, Genetic; D005810:Multigene Family / Q000235:genetics