Abstract: In this paper we develop a theory describing how the extended Burrows-Wheeler Transform (eBWT) of a collection of DNA fragments tends to cluster together the copies of nucleotides sequenced from a genome G. Our theory accurately predicts how many copies of any nucleotide are expected inside each such cluster, and how an elegant and precise LCP array based procedure can locate these clusters in the eBWT. Our findings are very general and can be applied to a wide range of different problems. In this paper, we consider the case of alignment-free and reference-free SNPs discovery in multiple collections of reads. We note that, in accordance with our theoretical results, SNPs are clustered in the eBWT of the reads collection, and we develop a tool finding SNPs with a simple scan of the eBWT and LCP arrays. Preliminary results show that our method requires much less coverage than state-of-the-art tools while drastically improving precision and sensitivity.
Recommendations
Cites work
- An extension of the Burrows-Wheeler transform
- Comparing DNA sequence collections by direct comparison of compressed text indexes
- scientific article; zbMATH DE number 432779 (Why is no real title available?)
- Inducing enhanced suffix arrays for string collections
- Lightweight algorithms for constructing and inverting the BWT of string collections
- Lightweight BWT and LCP merging via the gap algorithm
- Lightweight LCP construction for very large collections of strings
Cited in
(5)- Space-efficient construction of compressed suffix trees
- Comparing DNA sequence collections by direct comparison of compressed text indexes
- Space-efficient computation of the LCP array from the Burrows-Wheeler transform
- Analysis of min-hashing for variant tolerant DNA read mapping
- Data structures for SMEM-finding in the PBWT
This page was built for publication: Detecting mutations by eBWT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090327)
