Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Consistency of Sequence-Based Gene Clusters
verfasst von : Roland Wittler, Jens Stoye
Erschienen in: Comparative Genomics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In comparative genomics, various combinatorial models can be used to specify gene clusters — groups of genes that are co-located in a set of genomes. Several approaches have been proposed to reconstruct putative ancestral gene clusters based on the gene order of contemporary species. One prevalent and natural reconstruction criterion is
consistency
: For a set of reconstructed gene clusters, there should exist a gene order that comprises all given clusters.
In this paper, we discuss the consistency problem for different gene cluster models on sequences with restricted gene multiplicities. Our results range from linear-time algorithms for the simple model of
adjacencies
to NP completeness for more complex models like
common intervals
.