Approximation hardness and satisfiability of bounded occurrence instances of SAT, Electronic Colloquium on Computational Complexity (ECCC), vol.10, issue.022, 2003. ,
Repetitive DNA in eukaryotic genomes, Chromosome Res, vol.23, issue.3, pp.415-420, 2015. ,
GRIDSS: sensitive and specific genomic rearrangement detection using positional de Bruijn graph assembly, Genome Res, vol.27, issue.12, pp.2050-2060, 2017. ,
A complexity and approximation framework for the maximization scaffolding problem, Theoretical Computer Science, vol.595, pp.92-106, 2015. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01219622
Space-efficient and exact de Bruijn graph representation based on a Bloom filter, WABI, pp.236-248, 2012. ,
URL : https://hal.archives-ouvertes.fr/hal-00753930
A field guide to whole-genome sequencing, assembly and annotation, Evol Appl, vol.7, issue.9, pp.1026-1042, 2014. ,
Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979. ,
Some optimal inapproximability results, J. ACM, vol.48, issue.4, pp.798-859, 2001. ,
RepARK-de novo creation of repeat libraries from whole-genome NGS reads, Nucleic Acids Res, vol.42, issue.9, p.80, 2014. ,
Fast and accurate long-read alignment with BurrowsWheeler transform, Bioinformatics, vol.26, issue.5, pp.589-595, 2010. ,
The sequence alignment/map format and samtools, Bioinformatics, vol.25, issue.16, pp.2078-2079, 2009. ,
Planar formulae and their uses, SIAM Journal on Computing, vol.11, issue.2, pp.329-343, 1982. ,
Lower bounds based on the Exponential Time Hypothesis, Bulletin of the EATCS, vol.105, pp.41-72, 2011. ,
Scaffolding algorithms, Computational Methods for Next Generation Sequencing Data Analysis, pp.107-132, 2016. ,
Database indexing for production megablast searches, Bioinformatics, vol.24, issue.16, pp.1757-1764, 2008. ,
Optimization, approximation, and complexity classes, Journal of Computer and System Sciences, vol.43, issue.3, pp.425-440, 1991. ,
A tale of three next generation sequencing platforms: comparison of ion torrent, pacific biosciences and illumina miseq sequencers, BMC Genomics, vol.13, issue.1, p.341, 2012. ,
Genome assembly, rearrangement, and repeats, Chemical Reviews, vol.107, issue.8, pp.3391-3406, 2007. ,
Non-approximability results for optimization problems on bounded degree instances, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, pp.453-461, 2001. ,
Exact approaches for scaffolding, BMC Bioinformatics, vol.16, p.2, 2015. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01219627
On the linearization of scaffolds sharing repeated contigs, Proc. 11th COCOA'17, pp.509-517, 2017. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01672893
Scaffolding problems revisited: Complexity, approximation and fixed parameter tractable algorithms, and some special cases, Algorithmica, vol.80, issue.6, pp.1771-1803, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01833303
Scaffolding with repeated contigs using flow formulations, 2018. ,