Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Improved Algorithms for the Gene Team Problem
verfasst von : Biing-Feng Wang, Shang-Ju Liu, Chien-Hsin Lin
Erschienen in: Combinatorial Optimization and Applications
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
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
(
n
log
2
n
)-time algorithm for this problem. In this paper, two
O
(
n
log
d
)-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
(
kn
log
2
n
) time. Our improved algorithms can be extended to find the gene teams of
k
chromosomes in
O
(
kn
log
d
) time.