Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
A Polynomial Time Solution for Permutation Scaffold Filling
verfasst von : Nan Liu, Peng Zou, Binhai Zhu
Erschienen in: Combinatorial Optimization and Applications
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
Abstract
Recently, the scaffold filling problem has attracted a lot of attention due to its potential applications in processing incomplete genomic data. However, almost all the current research assumes that a scaffold is given as an incomplete sequence (i.e., missing genes can be inserted anywhere in the incomplete sequence). This differs significantly from most of the real genomic dataset, where a scaffold is given as a sequence of contigs. We show in this paper that when a scaffold is given as a sequence of contigs, and when the genome contains no duplication of genes, the corresponding scaffold filling problem, with the objective being maximizing the number of adjacencies between the filled scaffold and a complete reference genome, is polynomially solvable.