King's College London

Research portal

Parallelising the Computation of Minimal Absent Words

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

Standard

Parallelising the Computation of Minimal Absent Words. / Barton, Carl; Heliou, Alice; Mouchard, Laurent; Pissis, Solon P.

Parallel Processing and Applied Mathematics: 11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II. ed. / Roman Wyrzykowski; Ewa Deelman; Jack Dongarra; Konrad Karczewski; Jacek Kitowski; Kazimierz Wiatr. Vol. 9574 Springer (Reference), 2015. p. 243-253 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

Harvard

Barton, C, Heliou, A, Mouchard, L & Pissis, SP 2015, Parallelising the Computation of Minimal Absent Words. in R Wyrzykowski, E Deelman, J Dongarra, K Karczewski, J Kitowski & K Wiatr (eds), Parallel Processing and Applied Mathematics: 11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II. vol. 9574, Lecture Notes in Computer Science, Springer (Reference), pp. 243-253. https://doi.org/10.1007/978-3-319-32152-3_23

APA

Barton, C., Heliou, A., Mouchard, L., & Pissis, S. P. (2015). Parallelising the Computation of Minimal Absent Words. In R. Wyrzykowski, E. Deelman, J. Dongarra, K. Karczewski, J. Kitowski, & K. Wiatr (Eds.), Parallel Processing and Applied Mathematics: 11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II (Vol. 9574, pp. 243-253). (Lecture Notes in Computer Science). Springer (Reference). https://doi.org/10.1007/978-3-319-32152-3_23

Vancouver

Barton C, Heliou A, Mouchard L, Pissis SP. Parallelising the Computation of Minimal Absent Words. In Wyrzykowski R, Deelman E, Dongarra J, Karczewski K, Kitowski J, Wiatr K, editors, Parallel Processing and Applied Mathematics: 11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II. Vol. 9574. Springer (Reference). 2015. p. 243-253. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-32152-3_23

Author

Barton, Carl ; Heliou, Alice ; Mouchard, Laurent ; Pissis, Solon P. / Parallelising the Computation of Minimal Absent Words. Parallel Processing and Applied Mathematics: 11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II. editor / Roman Wyrzykowski ; Ewa Deelman ; Jack Dongarra ; Konrad Karczewski ; Jacek Kitowski ; Kazimierz Wiatr. Vol. 9574 Springer (Reference), 2015. pp. 243-253 (Lecture Notes in Computer Science).

Bibtex Download

@inbook{02c786a53af64c02b35a07cd07046ad8,
title = "Parallelising the Computation of Minimal Absent Words",
abstract = "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 array (Barton et al., 2014). An implementation of this algorithm was also provided by the authors and is currently the fastest available. In this article, we present a new O(n)-time and O(n)-space algorithm for computing all minimal absent words; it has the desirable property that, given the indexing data structure at hand, the computation of minimal absent words can be executed in parallel. Experimental results show that a multiprocessing implementation of this algorithm can accelerate the overall computation by more than a factor of two compared to state-of-the-art approaches. By excluding the indexing data structure construction time, we show that the implementation achieves near-optimal speed-ups.",
author = "Carl Barton and Alice Heliou and Laurent Mouchard and Pissis, {Solon P.}",
year = "2015",
month = apr,
day = "2",
doi = "10.1007/978-3-319-32152-3_23",
language = "English",
isbn = " 978331932156",
volume = "9574",
series = "Lecture Notes in Computer Science",
publisher = "Springer (Reference)",
pages = "243--253",
editor = "Roman Wyrzykowski and Ewa Deelman and Jack Dongarra and Konrad Karczewski and Jacek Kitowski and Kazimierz Wiatr",
booktitle = "Parallel Processing and Applied Mathematics",

}

RIS (suitable for import to EndNote) Download

TY - CHAP

T1 - Parallelising the Computation of Minimal Absent Words

AU - Barton, Carl

AU - Heliou, Alice

AU - Mouchard, Laurent

AU - Pissis, Solon P.

PY - 2015/4/2

Y1 - 2015/4/2

N2 - 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 array (Barton et al., 2014). An implementation of this algorithm was also provided by the authors and is currently the fastest available. In this article, we present a new O(n)-time and O(n)-space algorithm for computing all minimal absent words; it has the desirable property that, given the indexing data structure at hand, the computation of minimal absent words can be executed in parallel. Experimental results show that a multiprocessing implementation of this algorithm can accelerate the overall computation by more than a factor of two compared to state-of-the-art approaches. By excluding the indexing data structure construction time, we show that the implementation achieves near-optimal speed-ups.

AB - 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 array (Barton et al., 2014). An implementation of this algorithm was also provided by the authors and is currently the fastest available. In this article, we present a new O(n)-time and O(n)-space algorithm for computing all minimal absent words; it has the desirable property that, given the indexing data structure at hand, the computation of minimal absent words can be executed in parallel. Experimental results show that a multiprocessing implementation of this algorithm can accelerate the overall computation by more than a factor of two compared to state-of-the-art approaches. By excluding the indexing data structure construction time, we show that the implementation achieves near-optimal speed-ups.

U2 - 10.1007/978-3-319-32152-3_23

DO - 10.1007/978-3-319-32152-3_23

M3 - Other chapter contribution

SN - 978331932156

VL - 9574

T3 - Lecture Notes in Computer Science

SP - 243

EP - 253

BT - Parallel Processing and Applied Mathematics

A2 - Wyrzykowski, Roman

A2 - Deelman, Ewa

A2 - Dongarra, Jack

A2 - Karczewski, Konrad

A2 - Kitowski, Jacek

A2 - Wiatr, Kazimierz

PB - Springer (Reference)

ER -

View graph of relations

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