Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

This is an Open Access publication published under CSC-OpenAccess Policy.
Bliss: A New Read Overlap Detection Algorithm
Sayali Davalbhakta
Pages - 1 - 7     |    Revised - 10-07-2014     |    Published - 10-08-2014
Volume - 8   Issue - 1    |    Publication Date - August 2014  Table of Contents
Overlap Detection, De Novo Assembly, Overlap-layout-consensus, OLC Assemblers, DNA Sequencing, Whole Genome Shotgun Assembly.
Many assemblers carry out heuristic based overlap detection to avoid string comparisons. But heuristics skips many true overlaps. Also, the order of the number of read pairs compared for overlaps is higher than the order of n. In the raw approach it would be n 2 where every read is compared to every other read. Some assemblers have used a hybrid approach to bring the order down from n 2. Here is an algorithm which works with 100% accuracy. As there is no heuristics involved, it is able to report all the overlaps in a given set of reads without actual string comparisons. It achieves this purely by querying the k-mer position data. Moreover, the number of read pairs compared is proportional to the number of reads present i.e. of the order of n.
CITED BY (1)  
1 Davalbhakta, S. K. (2014). Read Overlap Detection in De Novo Assembly (Doctoral dissertation, department of computer engineering and information technology, college of engineering, pune).
1 Google Scholar
2 CiteSeerX
3 refSeek
4 Scribd
5 SlideShare
6 PdfSR
1 D. R. Zerbino and E. Birney. “Velvet: Algorithms for de novo short read assembly using de Bruijn graphs.” (2008) Genome Research, 18:821–829
2 Jeffrey J. Cook, Craig Zilles. “Characterizing and Optimizing the Memory Footprint of De Novo Short Read DNA Sequence Assembly” April, 2009.
3 Flicek P, Birney E. “Sense from sequence reads: methods for alignment and assembly.”Nat Methods. 2009 Nov;6(11 Suppl):S6-S12.
4 Ruiqiang Li, Hongmei Zhu, Jue Ruan, et al. (2009, December ). “De novo assembly of human genomes with massively parallel short read sequencing”, Genome Research,[Online].Available:http://genome.cshlp.org/content/early/2009/12/16/gr.097261.109.full.pdf+html
5 Birol I, Jackman SD, Nielsen CB, Qian JQ, Varhol R, Stazyk G, Morin RD, Zhao Y, Hirst M,Schein JE, Horsman DE, Connors JM, Gascoyne RD, Marra MA, Jones SJ. “De novo Transcriptome Assembly with ABySS” Bioinformatics (2009) 25 (21): 2872-2877.
6 Jared T. Simpson, Kim Wong, Shaun D. Jackman, Jacqueline E. Schein, Steven J.M.Jones, Inanc Birol. “ABySS: A parallel assembler for short read sequence data”, (2009)19(6):1117-23.
7 Chengxi Ye, Zhanshan (Sam) Ma, Charles H. Cannon, Mihai Pop, Douglas W. Yu.SparseAssembler: de novo Assembly with the Sparse de Bruijn Graph[Online].Available:http://arxiv.org/ftp/arxiv/papers/1106/1106.2603.pdf
8 Chengxi Ye, Charles H. Cannon, Zhanshan (Sam) Ma, Douglas W. Yu, Mihai Pop.SparseAssembler2: Sparse k-mer Graph for Memory Efficient Genome Assembly.[Online].Available:http://arxiv.org/ftp/arxiv/papers/1108/1108.3556.pdf
9 Serafim Batzoglou, David B. Jaffe, Ken Stanley, et al. “ARACHNE: A Whole-Genome Shotgun Assembler” (2002) Genome Research, 12:177–189.
10 Sayali Davalbhakta. “Throwing Away k-mer Strings” Submitted for publication.
Miss Sayali Davalbhakta
Department of Computer Engineering and IT College of Engineering, Pune Shivaji Nagar, 411005, India - India