Nov 7, 2018

BELLA: Berkeley Efficient Long-Read to Long-Read Aligner and Overlapper

BioRxiv : the Preprint Server for Biology
Giulia GuidiAyd?n Buluç

Abstract

Recent advances in long-read sequencing enable the characterization of genome structure and its intra- and inter-species variation at a resolution that was previously impossible. Detecting overlaps between reads is integral to many long-read genomics pipelines, such as de novo genome assembly. While longer reads simplify genome assembly and improve the contiguity of the reconstruction, current long-read technologies come with high error rates. We present Berkeley Long-Read to Long-Read Aligner and Overlapper (BELLA), a novel algorithm for computing overlaps and alignments via sparse matrix-matrix multiplication that balances the goals of recall and precision, performing well on both. We present a probabilistic model that demonstrates the feasibility of using short k-mers for detecting candidate overlaps. We then introduce a notion of reliable k-mers based on our probabilistic model. Combining reliable k-mers with our binning mechanism eliminates both the k-mer set explosion that would otherwise occur with highly erroneous reads and the spurious overlaps from k-mers originating in repetitive regions. Finally, we present a new method based on Chernoff bounds for separating true overlaps from false positives using a combination of...Continue Reading

  • References
  • Citations

References

  • We're still populating references for this paper, please check back later.
  • References
  • Citations

Citations

  • This paper may not have been cited yet.

Mentioned in this Paper

Severe Acute Respiratory Syndrome
Repetitive Region
Genome
Genome Assembly Sequence
C-Long
probe gene fragment
Drops - Drug Form
Calcaneal Apophysitis
Multilevel Analysis
HAL-2 protein, C elegans

About this Paper

Related Feeds

BioRxiv & MedRxiv Preprints

BioRxiv and MedRxiv are the preprint servers for biology and health sciences respectively, operated by Cold Spring Harbor Laboratory. Here are the latest preprint articles (which are not peer-reviewed) from BioRxiv and MedRxiv.

Related Papers

Journal of Human Genetics
Yoshitaka SakamotoAyako Suzuki
BioRxiv : the Preprint Server for Biology
Jue Ruan, Heng Li
© 2020 Meta ULC. All rights reserved