Producing Genomic Sequences after Genome Scaffolding with Ambiguous Paths: Complexity, Approximation and Lower Bounds.
Tom DavotAnnie ChateauRodolphe GiroudeauMathias WellerDorine TabaryPublished in: Algorithmica (2021)
Keyphrases
- genomic sequences
- lower bound
- dna sequences
- worst case
- approximation error
- upper bound
- genomic databases
- average case complexity
- gene prediction
- objective function
- polynomial approximation
- error tolerance
- decision problems
- branch and bound algorithm
- error bounds
- lower and upper bounds
- previously unknown
- human genome
- branch and bound
- linear programming relaxation
- shortest path
- prior knowledge
- approximation algorithms
- gene regulation
- np hard
- learning environment
- information retrieval