Cargando…
Variable-order reference-free variant discovery with the Burrows-Wheeler Transform
BACKGROUND: In [Prezza et al., AMB 2019], a new reference-free and alignment-free framework for the detection of SNPs was suggested and tested. The framework, based on the Burrows-Wheeler Transform (BWT), significantly improves sensitivity and precision of previous de Bruijn graphs based tools by ov...
Autores principales: | , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2020
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7493873/ https://www.ncbi.nlm.nih.gov/pubmed/32938358 http://dx.doi.org/10.1186/s12859-020-03586-3 |
_version_ | 1783582644762574848 |
---|---|
author | Prezza, Nicola Pisanti, Nadia Sciortino, Marinella Rosone, Giovanna |
author_facet | Prezza, Nicola Pisanti, Nadia Sciortino, Marinella Rosone, Giovanna |
author_sort | Prezza, Nicola |
collection | PubMed |
description | BACKGROUND: In [Prezza et al., AMB 2019], a new reference-free and alignment-free framework for the detection of SNPs was suggested and tested. The framework, based on the Burrows-Wheeler Transform (BWT), significantly improves sensitivity and precision of previous de Bruijn graphs based tools by overcoming several of their limitations, namely: (i) the need to establish a fixed value, usually small, for the order k, (ii) the loss of important information such as k-mer coverage and adjacency of k-mers within the same read, and (iii) bad performance in repeated regions longer than k bases. The preliminary tool, however, was able to identify only SNPs and it was too slow and memory consuming due to the use of additional heavy data structures (namely, the Suffix and LCP arrays), besides the BWT. RESULTS: In this paper, we introduce a new algorithm and the corresponding tool ebwt2InDel that (i) extend the framework of [Prezza et al., AMB 2019] to detect also INDELs, and (ii) implements recent algorithmic findings that allow to perform the whole analysis using just the BWT, thus reducing the working space by one order of magnitude and allowing the analysis of full genomes. Finally, we describe a simple strategy for effectively parallelizing our tool for SNP detection only. On a 24-cores machine, the parallel version of our tool is one order of magnitude faster than the sequential one. The tool ebwt2InDel is available at github.com/nicolaprezza/ebwt2InDel. CONCLUSIONS: Results on a synthetic dataset covered at 30x (Human chromosome 1) show that our tool is indeed able to find up to 83% of the SNPs and 72% of the existing INDELs. These percentages considerably improve the 71% of SNPs and 51% of INDELs found by the state-of-the art tool based on de Bruijn graphs. We furthermore report results on larger (real) Human whole-genome sequencing experiments. Also in these cases, our tool exhibits a much higher sensitivity than the state-of-the art tool. |
format | Online Article Text |
id | pubmed-7493873 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2020 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-74938732020-09-23 Variable-order reference-free variant discovery with the Burrows-Wheeler Transform Prezza, Nicola Pisanti, Nadia Sciortino, Marinella Rosone, Giovanna BMC Bioinformatics Research BACKGROUND: In [Prezza et al., AMB 2019], a new reference-free and alignment-free framework for the detection of SNPs was suggested and tested. The framework, based on the Burrows-Wheeler Transform (BWT), significantly improves sensitivity and precision of previous de Bruijn graphs based tools by overcoming several of their limitations, namely: (i) the need to establish a fixed value, usually small, for the order k, (ii) the loss of important information such as k-mer coverage and adjacency of k-mers within the same read, and (iii) bad performance in repeated regions longer than k bases. The preliminary tool, however, was able to identify only SNPs and it was too slow and memory consuming due to the use of additional heavy data structures (namely, the Suffix and LCP arrays), besides the BWT. RESULTS: In this paper, we introduce a new algorithm and the corresponding tool ebwt2InDel that (i) extend the framework of [Prezza et al., AMB 2019] to detect also INDELs, and (ii) implements recent algorithmic findings that allow to perform the whole analysis using just the BWT, thus reducing the working space by one order of magnitude and allowing the analysis of full genomes. Finally, we describe a simple strategy for effectively parallelizing our tool for SNP detection only. On a 24-cores machine, the parallel version of our tool is one order of magnitude faster than the sequential one. The tool ebwt2InDel is available at github.com/nicolaprezza/ebwt2InDel. CONCLUSIONS: Results on a synthetic dataset covered at 30x (Human chromosome 1) show that our tool is indeed able to find up to 83% of the SNPs and 72% of the existing INDELs. These percentages considerably improve the 71% of SNPs and 51% of INDELs found by the state-of-the art tool based on de Bruijn graphs. We furthermore report results on larger (real) Human whole-genome sequencing experiments. Also in these cases, our tool exhibits a much higher sensitivity than the state-of-the art tool. BioMed Central 2020-09-16 /pmc/articles/PMC7493873/ /pubmed/32938358 http://dx.doi.org/10.1186/s12859-020-03586-3 Text en © The Author(s) 2020 Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated in a credit line to the data. |
spellingShingle | Research Prezza, Nicola Pisanti, Nadia Sciortino, Marinella Rosone, Giovanna Variable-order reference-free variant discovery with the Burrows-Wheeler Transform |
title | Variable-order reference-free variant discovery with the Burrows-Wheeler Transform |
title_full | Variable-order reference-free variant discovery with the Burrows-Wheeler Transform |
title_fullStr | Variable-order reference-free variant discovery with the Burrows-Wheeler Transform |
title_full_unstemmed | Variable-order reference-free variant discovery with the Burrows-Wheeler Transform |
title_short | Variable-order reference-free variant discovery with the Burrows-Wheeler Transform |
title_sort | variable-order reference-free variant discovery with the burrows-wheeler transform |
topic | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7493873/ https://www.ncbi.nlm.nih.gov/pubmed/32938358 http://dx.doi.org/10.1186/s12859-020-03586-3 |
work_keys_str_mv | AT prezzanicola variableorderreferencefreevariantdiscoverywiththeburrowswheelertransform AT pisantinadia variableorderreferencefreevariantdiscoverywiththeburrowswheelertransform AT sciortinomarinella variableorderreferencefreevariantdiscoverywiththeburrowswheelertransform AT rosonegiovanna variableorderreferencefreevariantdiscoverywiththeburrowswheelertransform |