Advanced search
1 file | 461.30 KB

Prospects and limitations of full-text index structures in genome analysis

Michaël Vyverman (UGent) , Bernard De Baets (UGent) , Veerle Fack (UGent) and Peter Dawyndt (UGent)
(2012) NUCLEIC ACIDS RESEARCH. 40(15). p.6993-7015
Author
Organization
Project
Bioinformatics: from nucleotids to networks (N2N)
Abstract
The combination of incessant advances in sequencing technology producing large amounts of data and innovative bioinformatics approaches, designed to cope with this data flood, has led to new interesting results in the life sciences. Given the magnitude of sequence data to be processed, many bioinformatics tools rely on efficient solutions to a variety of complex string problems. These solutions include fast heuristic algorithms and advanced data structures, generally referred to as index structures. Although the importance of index structures is generally known to the bioinformatics community, the design and potency of these data structures, as well as their properties and limitations, are less understood. Moreover, the last decade has seen a boom in the number of variant index structures featuring complex and diverse memory-time trade-offs. This article brings a comprehensive state-of-the-art overview of the most popular index structures and their recently developed variants. Their features, interrelationships, the trade-offs they impose, but also their practical limitations, are explained and compared.
Keywords
SHORT READ ALIGNMENT, COMPRESSED SUFFIX ARRAYS, EXTERNAL MEMORY, TREE CONSTRUCTION, FM-INDEX, EFFICIENT CONSTRUCTION, SEQUENCE COLLECTIONS, PRACTICAL ALGORITHM, INVERTED FILES, MASSIVE DATA

Downloads

  • KERMIT-A1-267.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 461.30 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Vyverman, Michaël, Bernard De Baets, Veerle Fack, and Peter Dawyndt. 2012. “Prospects and Limitations of Full-text Index Structures in Genome Analysis.” Nucleic Acids Research 40 (15): 6993–7015.
APA
Vyverman, M., De Baets, B., Fack, V., & Dawyndt, P. (2012). Prospects and limitations of full-text index structures in genome analysis. NUCLEIC ACIDS RESEARCH, 40(15), 6993–7015.
Vancouver
1.
Vyverman M, De Baets B, Fack V, Dawyndt P. Prospects and limitations of full-text index structures in genome analysis. NUCLEIC ACIDS RESEARCH. 2012;40(15):6993–7015.
MLA
Vyverman, Michaël, Bernard De Baets, Veerle Fack, et al. “Prospects and Limitations of Full-text Index Structures in Genome Analysis.” NUCLEIC ACIDS RESEARCH 40.15 (2012): 6993–7015. Print.
@article{2974977,
  abstract     = {The combination of incessant advances in sequencing technology producing large amounts of data and innovative bioinformatics approaches, designed to cope with this data flood, has led to new interesting results in the life sciences. Given the magnitude of sequence data to be processed, many bioinformatics tools rely on efficient solutions to a variety of complex string problems. These solutions include fast heuristic algorithms and advanced data structures, generally referred to as index structures. Although the importance of index structures is generally known to the bioinformatics community, the design and potency of these data structures, as well as their properties and limitations, are less understood. Moreover, the last decade has seen a boom in the number of variant index structures featuring complex and diverse memory-time trade-offs. This article brings a comprehensive state-of-the-art overview of the most popular index structures and their recently developed variants. Their features, interrelationships, the trade-offs they impose, but also their practical limitations, are explained and compared.},
  author       = {Vyverman, Micha{\"e}l and De Baets, Bernard and Fack, Veerle and Dawyndt, Peter},
  issn         = {0305-1048},
  journal      = {NUCLEIC ACIDS RESEARCH},
  language     = {eng},
  number       = {15},
  pages        = {6993--7015},
  title        = {Prospects and limitations of full-text index structures in genome analysis},
  url          = {http://dx.doi.org/10.1093/nar/gks408},
  volume       = {40},
  year         = {2012},
}

Altmetric
View in Altmetric
Web of Science
Times cited: