Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Gene Assembly Algorithms for Ciliates
verfasst von : Lucian Ilie, Roberto Solis-Oba
Erschienen in: DNA Computing
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
The micronuclear genes in stichotrichous ciliates are interrupted by multiple non-coding DNA segments. The coding segments are in scrambled disorder and can also be inverted. Identical short sequences (pointers) at the ends of the coding segments undergo homologous recombination to excise the non-coding segments and splice the coding ones. We consider the intramolecular model of Prescott, Ehrenfeucht, and Rozenberg for gene assembly in stichotrichous ciliates from the algorithmic point of view. We give a quadratic time algorithm for finding a successful sequence of operations to assemble a gene. We also prove an Ω(
n
log
n
) lower bound on the amount of work needed to assemble genes, even when any pair of identical pointers have the same orientation. For the problem of finding the minimum number of operations needed to assemble a given gene, we give a heuristic quadratic algorithm which works well in practice. The complexity of this problem remains open.