title: Efficient and scalable scaffolding using optical restriction maps.
abstract: In the next generation sequencing techniques millions of short reads are produced from a genomic sequence at a single run. The chances of low read coverage to some regions of the sequence are very high. The reads are short and very large in number. Due to erroneous base calling, there could be errors in the reads. As a consequence, sequence assemblers often fail to sequence an entire DNA molecule and instead output a set of overlapping segments that together represent a consensus region of the DNA. This set of overlapping segments are collectively called contigs in the literature. The final step of the sequencing process, called scaffolding, is to assemble the contigs into a correct order. Scaffolding techniques typically exploit additional information such as mate-pairs, pair-ends, or optical restriction maps. In this paper we introduce a series of novel algorithms for scaffolding that exploit optical restriction maps (ORMs). Simulation results show that our algorithms are indeed reliable, scalable, and efficient compared to the best known algorithms in the literature.
authors.forename: Subrata
authors.initials: S
authors.lastname: Saha
authors.forename: Sanguthevar
authors.initials: S
authors.lastname: Rajasekaran
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D020451:Contig Mapping; D016680:Genome, Bacterial; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D015007:Yersinia / Q000235:genetics
references.citation: Genome Res. 1995 Aug;5(1):1-4
references.pmid: 8717049
references.citation: Genome Res. 2012 Mar;22(3):549-56
references.pmid: 22156294
references.citation: Nucleic Acids Res. 1979 Jun 11;6(7):2601-10
references.pmid: 461197
references.citation: Bioinformatics. 2008 May 15;24(10):1229-35
references.pmid: 18356192
references.citation: Genome Res. 2003 Sep;13(9):2152-63
references.pmid: 12915486
references.citation: J Comput Biol. 2003;10(3-4):385-98
references.pmid: 12935335
references.citation: Annu Rev Biochem. 1975;44:273-93
references.pmid: 166604
references.citation: Proc Natl Acad Sci U S A. 1977 Dec;74(12):5463-7
references.pmid: 271968
references.citation: Nucleic Acids Res. 1981 Jul 10;9(13):3015-27
references.pmid: 6269069
references.citation: Appl Environ Microbiol. 2005 Sep;71(9):5511-22
references.pmid: 16151144
references.citation: Trends Genet. 2008 Mar;24(3):142-9
references.pmid: 18262676
references.citation: J Mol Biol. 1975 May 25;94(3):441-8
references.pmid: 1100841
references.citation: Genome Biol. 2004;5(2):R12
references.pmid: 14759262
references.citation: Nat Rev Genet. 2010 Jan;11(1):31-46
references.pmid: 19997069
references.citation: Genome Res. 2009 Feb;19(2):336-46
references.pmid: 19056694
references.citation: Nat Rev Genet. 2009 Apr;10(4):241-51
references.pmid: 19293820