Hypergraph covering problems motivated by genome assembly questions
Preprint
Abstract
The Consecutive-Ones Property (C1P) is a classical concept in discrete mathematics that has been used in several genomics applications, from physical mapping of contemporary genomes to the assembly of ancient genomes. A common issue in genome assembly concerns repeats, genomic sequences that appear in several locations of a genome. Handling repeats leads to a variant of the C1P, the C1P with multiplicity (mC1P), that can also be seen as the problem of covering edges of hypergraphs by linear and circular walks. In the present work, we describe variants of the mC1P that address specific issues of genome assembly, and polynomial time or fixed-parameter algorithms to solve them.Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- Hardness results on the gapped consecutive-ones property problemDiscrete Applied Mathematics, 2012
- Hybrid error correction and de novo assembly of single-molecule sequencing readsNature Biotechnology, 2012
- FinIS: Improved in silico Finishing Using an Exact Quadratic Programming FormulationLecture Notes in Computer Science, 2012
- Radiation Hybrid Map Construction Problem ParameterizedLecture Notes in Computer Science, 2012
- Tractability Results for the Consecutive-Ones Property with MultiplicityLecture Notes in Computer Science, 2011
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problemsJournal of Computer and System Sciences, 2010
- Detecting Repeat Families in Incompletely Sequenced Genomes2008
- Computability of Models for Sequence Assembly2007
- Physical Mapping with Repeated Probes: The Hypergraph Superstring ProblemLecture Notes in Computer Science, 1999
- Combinatorial algorithms for DNA sequence assemblyAlgorithmica, 1995