A bioinformatician’s guide to the forefront of suffix array construction algorithms

The suffix array and its variants are text-indexing data structures that have become indispensable in the field of bioinformatics. With the uninitiated in mind, we provide an accessible exposition of the SA-IS algorithm, which is the state of the art in suffix array construction. We also describe Di...

Descripción completa

Detalles Bibliográficos
Autores principales: Shrestha, Anish Man Singh, Frith, Martin C., Horton, Paul
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Oxford University Press 2014
Materias:
Papers
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3956071/
https://www.ncbi.nlm.nih.gov/pubmed/24413184
http://dx.doi.org/10.1093/bib/bbt081
_version_ 1782307646840242176
author Shrestha, Anish Man Singh
Frith, Martin C.
Horton, Paul
author_facet Shrestha, Anish Man Singh
Frith, Martin C.
Horton, Paul
author_sort Shrestha, Anish Man Singh
collection PubMed
description The suffix array and its variants are text-indexing data structures that have become indispensable in the field of bioinformatics. With the uninitiated in mind, we provide an accessible exposition of the SA-IS algorithm, which is the state of the art in suffix array construction. We also describe DisLex, a technique that allows standard suffix array construction algorithms to create modified suffix arrays designed to enable a simple form of inexact matching needed to support ‘spaced seeds’ and ‘subset seeds’ used in many biological applications.
format Online
Article
Text
id pubmed-3956071
institution National Center for Biotechnology Information
language English
publishDate 2014
publisher Oxford University Press
record_format MEDLINE/PubMed
spelling pubmed-39560712014-06-18 A bioinformatician’s guide to the forefront of suffix array construction algorithms Shrestha, Anish Man Singh Frith, Martin C. Horton, Paul Brief Bioinform Papers The suffix array and its variants are text-indexing data structures that have become indispensable in the field of bioinformatics. With the uninitiated in mind, we provide an accessible exposition of the SA-IS algorithm, which is the state of the art in suffix array construction. We also describe DisLex, a technique that allows standard suffix array construction algorithms to create modified suffix arrays designed to enable a simple form of inexact matching needed to support ‘spaced seeds’ and ‘subset seeds’ used in many biological applications. Oxford University Press 2014-03 2014-01-10 /pmc/articles/PMC3956071/ /pubmed/24413184 http://dx.doi.org/10.1093/bib/bbt081 Text en © The Author 2014. Published by Oxford University Press. http://creativecommons.org/licenses/by/3.0/ This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Papers
Shrestha, Anish Man Singh
Frith, Martin C.
Horton, Paul
A bioinformatician’s guide to the forefront of suffix array construction algorithms
title A bioinformatician’s guide to the forefront of suffix array construction algorithms
title_full A bioinformatician’s guide to the forefront of suffix array construction algorithms
title_fullStr A bioinformatician’s guide to the forefront of suffix array construction algorithms
title_full_unstemmed A bioinformatician’s guide to the forefront of suffix array construction algorithms
title_short A bioinformatician’s guide to the forefront of suffix array construction algorithms
title_sort bioinformatician’s guide to the forefront of suffix array construction algorithms
topic Papers
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3956071/
https://www.ncbi.nlm.nih.gov/pubmed/24413184
http://dx.doi.org/10.1093/bib/bbt081
work_keys_str_mv AT shresthaanishmansingh abioinformaticiansguidetotheforefrontofsuffixarrayconstructionalgorithms
AT frithmartinc abioinformaticiansguidetotheforefrontofsuffixarrayconstructionalgorithms
AT hortonpaul abioinformaticiansguidetotheforefrontofsuffixarrayconstructionalgorithms
AT shresthaanishmansingh bioinformaticiansguidetotheforefrontofsuffixarrayconstructionalgorithms
AT frithmartinc bioinformaticiansguidetotheforefrontofsuffixarrayconstructionalgorithms
AT hortonpaul bioinformaticiansguidetotheforefrontofsuffixarrayconstructionalgorithms

Ejemplares similares