King's College London

Research portal

Parallelising the Computation of Minimal Absent Words

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

Original languageEnglish
Title of host publicationParallel Processing and Applied Mathematics
Subtitle of host publication11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II
EditorsRoman Wyrzykowski, Ewa Deelman, Jack Dongarra, Konrad Karczewski, Jacek Kitowski, Kazimierz Wiatr
PublisherSpringer (Reference)
Pages243-253
Number of pages11
Volume9574
ISBN (Electronic)9783319321523
ISBN (Print) 978331932156
DOIs
Publication statusPublished - 2 Apr 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer

King's Authors

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.

View graph of relations

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