Bliss: A New Read Overlap Detection Algorithm

International Journal of Biometric and Bioinformatics

Sayali Davalbhakta¹ 

关键词: Overlap Detection;    De Novo Assembly;    Overlap-layout-consensus;    OLC Assemblers;    DNA Sequencing;    Whole Genome Shotgun Assembly.;   

DOI  :  

学科分类：计算机科学（综合）

来源: Computer Science Journals

【 摘 要 】

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.

【 授权许可】

Unknown