Cargando…
A random-permutations-based approach to fast read alignment
BACKGROUND: Read alignment is a computational bottleneck in some sequencing projects. Most of the existing software packages for read alignment are based on two algorithmic approaches: prefix-trees and hash-tables. We propose a new approach to read alignment using random permutations of strings. RES...
Autor principal: | |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2013
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3622637/ https://www.ncbi.nlm.nih.gov/pubmed/23734846 http://dx.doi.org/10.1186/1471-2105-14-S5-S8 |
_version_ | 1782265858740977664 |
---|---|
author | Lederman, Roy |
author_facet | Lederman, Roy |
author_sort | Lederman, Roy |
collection | PubMed |
description | BACKGROUND: Read alignment is a computational bottleneck in some sequencing projects. Most of the existing software packages for read alignment are based on two algorithmic approaches: prefix-trees and hash-tables. We propose a new approach to read alignment using random permutations of strings. RESULTS: We present a prototype implementation and experiments performed with simulated and real reads of human DNA. Our experiments indicate that this permutations-based prototype is several times faster than comparable programs for fast read alignment and that it aligns more reads correctly. CONCLUSIONS: This approach may lead to improved speed, sensitivity, and accuracy in read alignment. The algorithm can also be used for specialized alignment applications and it can be extended to other related problems, such as assembly. More information: http://alignment.commons.yale.edu |
format | Online Article Text |
id | pubmed-3622637 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2013 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-36226372013-04-15 A random-permutations-based approach to fast read alignment Lederman, Roy BMC Bioinformatics Proceedings BACKGROUND: Read alignment is a computational bottleneck in some sequencing projects. Most of the existing software packages for read alignment are based on two algorithmic approaches: prefix-trees and hash-tables. We propose a new approach to read alignment using random permutations of strings. RESULTS: We present a prototype implementation and experiments performed with simulated and real reads of human DNA. Our experiments indicate that this permutations-based prototype is several times faster than comparable programs for fast read alignment and that it aligns more reads correctly. CONCLUSIONS: This approach may lead to improved speed, sensitivity, and accuracy in read alignment. The algorithm can also be used for specialized alignment applications and it can be extended to other related problems, such as assembly. More information: http://alignment.commons.yale.edu BioMed Central 2013-04-10 /pmc/articles/PMC3622637/ /pubmed/23734846 http://dx.doi.org/10.1186/1471-2105-14-S5-S8 Text en Copyright © 2013 Lederman; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Proceedings Lederman, Roy A random-permutations-based approach to fast read alignment |
title | A random-permutations-based approach to fast read alignment |
title_full | A random-permutations-based approach to fast read alignment |
title_fullStr | A random-permutations-based approach to fast read alignment |
title_full_unstemmed | A random-permutations-based approach to fast read alignment |
title_short | A random-permutations-based approach to fast read alignment |
title_sort | random-permutations-based approach to fast read alignment |
topic | Proceedings |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3622637/ https://www.ncbi.nlm.nih.gov/pubmed/23734846 http://dx.doi.org/10.1186/1471-2105-14-S5-S8 |
work_keys_str_mv | AT ledermanroy arandompermutationsbasedapproachtofastreadalignment AT ledermanroy randompermutationsbasedapproachtofastreadalignment |