Home   >   CSC-OpenAccess Library   >    Manuscript Information
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
MORE INFORMATION
KEYWORDS
Overlap Detection, De Novo Assembly, Overlap-layout-consensus, OLC Assemblers, DNA Sequencing, Whole Genome Shotgun Assembly.
ABSTRACT
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 
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.
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
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
D. R. Zerbino and E. Birney. “Velvet: Algorithms for de novo short read assembly using de Bruijn graphs.” (2008) Genome Research, 18:821–829
Flicek P, Birney E. “Sense from sequence reads: methods for alignment and assembly.”Nat Methods. 2009 Nov;6(11 Suppl):S6-S12.
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.
Jeffrey J. Cook, Craig Zilles. “Characterizing and Optimizing the Memory Footprint of De Novo Short Read DNA Sequence Assembly” April, 2009.
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
Sayali Davalbhakta. “Throwing Away k-mer Strings” Submitted for publication.
Serafim Batzoglou, David B. Jaffe, Ken Stanley, et al. “ARACHNE: A Whole-Genome Shotgun Assembler” (2002) Genome Research, 12:177–189.
Miss Sayali Davalbhakta
Department of Computer Engineering and IT College of Engineering, Pune Shivaji Nagar, 411005, India - India
sayalid@gmail.com


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS