Identifying Conserved Gene Clusters in the Presence of Homology Families
Publication: Journal of Computational Biology
Volume 12, Issue Number 6
Abstract
The study of conserved gene clusters is important for understanding the forces behind genome organization and evolution, as well as the function of individual genes or gene groups. In this paper, we present a new model and algorithm for identifying conserved gene clusters from pairwise genome comparison. This generalizes a recent model called "gene teams." A gene team is a set of genes that appear homologously in two or more species, possibly in a different order yet with the distance of adjacent genes in the team for each chromosome always no more than a certain threshold. We remove the constraint in the original model that each gene must have a unique occurrence in each chromosome and thus allow the analysis on complex prokaryotic or eukaryotic genomes with extensive paralogs. Our algorithm analyzes a pair of chromosomes in O(mn) time and uses O(m+n) space, where m and n are the number of genes in the respective chromosomes. We demonstrate the utility of our methods by studying two bacterial genomes, E. coli K-12 and B. subtilis. Many of the teams identified by our algorithm correlate with documented E. coli operons, while several others match predicted operons, previously suggested by computational techniques. Our implementation and data are publicly available at euler.slu.edu/∼goldwasser/homologyteams/.
Get full access to this article
View all available purchase options and get full access to this article.
Information & Authors
Information
Published In
Journal of Computational Biology
Volume 12 • Issue Number 6 • July/August 2005
Pages: 638 - 656
PubMed: 16108708
Copyright
Copyright 2005, Mary Ann Liebert, Inc.
History
Published online: 18 August 2005
Published in print: July/August 2005
Topics
Authors
Metrics & Citations
Metrics
Citations
Export Citation
Export citation
Select the format you want to export the citations of this publication.
View Options
Access content
To read the fulltext, please use one of the options below to sign in or purchase access.⚠ Society Access
If you are a member of a society that has access to this content please log in via your society website and then return to this publication.