King's College London

Research portal

Linear-time computation of minimal absent words using suffix array

Research output: Contribution to journalArticle

Standard

Linear-time computation of minimal absent words using suffix array. / Barton, Carl; Heliou, Alice; Mouchard, Laurent; Pissis, Solon P.

In: BMC Bioinformatics, Vol. 15, No. 1, 388, 12.2014.

Research output: Contribution to journalArticle

Harvard

Barton, C, Heliou, A, Mouchard, L & Pissis, SP 2014, 'Linear-time computation of minimal absent words using suffix array', BMC Bioinformatics, vol. 15, no. 1, 388. https://doi.org/10.1186/1471-2105-15-388

APA

Barton, C., Heliou, A., Mouchard, L., & Pissis, S. P. (2014). Linear-time computation of minimal absent words using suffix array. BMC Bioinformatics, 15(1), [388]. https://doi.org/10.1186/1471-2105-15-388

Vancouver

Barton C, Heliou A, Mouchard L, Pissis SP. Linear-time computation of minimal absent words using suffix array. BMC Bioinformatics. 2014 Dec;15(1). 388. https://doi.org/10.1186/1471-2105-15-388

Author

Barton, Carl ; Heliou, Alice ; Mouchard, Laurent ; Pissis, Solon P. / Linear-time computation of minimal absent words using suffix array. In: BMC Bioinformatics. 2014 ; Vol. 15, No. 1.

Bibtex Download

@article{9ebf56c676e24093bbbb47110c81a5e8,
title = "Linear-time computation of minimal absent words using suffix array",
abstract = "Background:An absent word of a word y of length n is a word that does not occur in y. It is a minimal absent word if all its proper factors occur in y. Minimal absent words have been computed in genomes of organisms from all domains of life; their computation also provides a fast alternative for measuring approximation in sequence comparison. There exists an O(n) -time and O(n) -space algorithm for computing all minimal absent words on a fixed-sized alphabet based on the construction of suffix automata (Crochemore et al., 1998). No implementation of this algorithm is publicly available. There also exists an O(n2) -time and O(n) -space algorithm for the same problem based on the construction of suffix arrays (Pinho et al., 2009). An implementation of this algorithm was also provided by the authors and is currently the fastest available.Results:Our contribution in this article is twofold: first, we bridge this unpleasant gap by presenting an O(n) -time and O(n) -space algorithm for computing all minimal absent words based on the construction of suffix arrays; and second, we provide the respective implementation of this algorithm. Experimental results, using real and synthetic data, show that this implementation outperforms the one by Pinho et al. The open-source code of our implementation is freely available at http://github.com/solonas13/maw.Conclusions:Classical notions for sequence comparison are increasingly being replaced by other similarity measures that refer to the composition of sequences in terms of their constituent patterns. One such measure is the minimal absent words. In this article, we present a new linear-time and linear-space algorithm for the computation of minimal absent words based on the suffix array.",
author = "Carl Barton and Alice Heliou and Laurent Mouchard and Pissis, {Solon P.}",
year = "2014",
month = dec,
doi = "10.1186/1471-2105-15-388",
language = "English",
volume = "15",
journal = "BMC Bioinformatics",
issn = "1471-2105",
publisher = "BioMed Central",
number = "1",

}

RIS (suitable for import to EndNote) Download

TY - JOUR

T1 - Linear-time computation of minimal absent words using suffix array

AU - Barton, Carl

AU - Heliou, Alice

AU - Mouchard, Laurent

AU - Pissis, Solon P.

PY - 2014/12

Y1 - 2014/12

N2 - Background:An absent word of a word y of length n is a word that does not occur in y. It is a minimal absent word if all its proper factors occur in y. Minimal absent words have been computed in genomes of organisms from all domains of life; their computation also provides a fast alternative for measuring approximation in sequence comparison. There exists an O(n) -time and O(n) -space algorithm for computing all minimal absent words on a fixed-sized alphabet based on the construction of suffix automata (Crochemore et al., 1998). No implementation of this algorithm is publicly available. There also exists an O(n2) -time and O(n) -space algorithm for the same problem based on the construction of suffix arrays (Pinho et al., 2009). An implementation of this algorithm was also provided by the authors and is currently the fastest available.Results:Our contribution in this article is twofold: first, we bridge this unpleasant gap by presenting an O(n) -time and O(n) -space algorithm for computing all minimal absent words based on the construction of suffix arrays; and second, we provide the respective implementation of this algorithm. Experimental results, using real and synthetic data, show that this implementation outperforms the one by Pinho et al. The open-source code of our implementation is freely available at http://github.com/solonas13/maw.Conclusions:Classical notions for sequence comparison are increasingly being replaced by other similarity measures that refer to the composition of sequences in terms of their constituent patterns. One such measure is the minimal absent words. In this article, we present a new linear-time and linear-space algorithm for the computation of minimal absent words based on the suffix array.

AB - Background:An absent word of a word y of length n is a word that does not occur in y. It is a minimal absent word if all its proper factors occur in y. Minimal absent words have been computed in genomes of organisms from all domains of life; their computation also provides a fast alternative for measuring approximation in sequence comparison. There exists an O(n) -time and O(n) -space algorithm for computing all minimal absent words on a fixed-sized alphabet based on the construction of suffix automata (Crochemore et al., 1998). No implementation of this algorithm is publicly available. There also exists an O(n2) -time and O(n) -space algorithm for the same problem based on the construction of suffix arrays (Pinho et al., 2009). An implementation of this algorithm was also provided by the authors and is currently the fastest available.Results:Our contribution in this article is twofold: first, we bridge this unpleasant gap by presenting an O(n) -time and O(n) -space algorithm for computing all minimal absent words based on the construction of suffix arrays; and second, we provide the respective implementation of this algorithm. Experimental results, using real and synthetic data, show that this implementation outperforms the one by Pinho et al. The open-source code of our implementation is freely available at http://github.com/solonas13/maw.Conclusions:Classical notions for sequence comparison are increasingly being replaced by other similarity measures that refer to the composition of sequences in terms of their constituent patterns. One such measure is the minimal absent words. In this article, we present a new linear-time and linear-space algorithm for the computation of minimal absent words based on the suffix array.

U2 - 10.1186/1471-2105-15-388

DO - 10.1186/1471-2105-15-388

M3 - Article

VL - 15

JO - BMC Bioinformatics

JF - BMC Bioinformatics

SN - 1471-2105

IS - 1

M1 - 388

ER -

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454