Main menu

Overlap detection on long, error-prone sequencing reads via smooth q-gram


Motivation

Third generation sequencing techniques, such as the Single Molecule Real Time technique from PacBio and the MinION technique from Oxford Nanopore, can generate long, error-prone sequencing reads which pose new challenges for fragment assembly algorithms. In this paper, we study the overlap detection problem for error-prone reads, which is the first and most critical step in the de novo fragment assembly.

We observe that all the state-of-the-art methods cannot achieve an ideal accuracy for overlap detection (in terms of relatively low precision and recall) due to the high sequencing error rates, especially when the overlap lengths between reads are relatively short (e.g. <2000 bases). This limitation appears inherent to these algorithms due to their usage of q-gram-based seeds under the seed-extension framework.

Results

We propose smooth q-gram, a variant of q-gram that captures q-gram pairs within small edit distances and design a novel algorithm for detecting overlapping reads using smooth q-gram-based seeds. We implemented the algorithm and tested it on both PacBio and Nanopore sequencing datasets. Our benchmarking results demonstrated that our algorithm outperforms the existing q-gram-based overlap detection algorithms, especially for reads with relatively short overlapping lengths.

Authors: Yan Song, Haixu Tang, Haoyu Zhang, Qin Zhang

入門

MinION Starter Packを購入 ナノポア製品の販売 シークエンスサービスプロバイダー グローバルディストリビューター

ナノポア技術

ナノポアの最新ニュースを購読 リソースと発表文献 Nanopore Communityとは

Oxford Nanoporeについて

ニュース 会社沿革 持続可能性 経営陣 メディアリソース & お問い合わせ先 投資家向け パートナー向け Oxford Nanopore社で働く 現在の募集状況 営業上の情報 BSI 27001 accreditationBSI 90001 accreditationBSI mark of trust
Japanese flag