In this paper, we present the SECURED project11Funded in part by the European Union (EU), Grant Agreement no. 10109571. Views and opinions expressed are those of the authors and do not necessarily reflect those of the EU or the Health and Digital Executive Agency. Neither the EU nor the granting authority are responsible for them., aimed at improving privacy-preserving processing of data in the health domain. The technologies developed in the project will be demonstrated in four health-related use cases and with the involvement of SME's selected through an open funding call.

Abstract A wordxthat is absent from a wordyis calledminimalif all its proper factors occur iny. Given a collection ofkwordsy1, … ,ykover an alphabetΣ, we are asked to compute the set $\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$ M{y1,…,yk}ℓ of minimal absent words of length at mostℓof the collection {y1, … ,yk}. The set $\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$ M{y1,…,yk}ℓ contains all the wordsxsuch thatxis absent from all the words of the collection while there existi,j, such that the maximal proper suffix ofxis a factor ofyiand the maximal proper prefix ofxis a factor ofyj. In data compression, this corresponds to computing the antidictionary ofkdocuments. In bioinformatics, it corresponds to computing words that are absent from a genome ofkchromosomes. Indeed, the set $\mathrm {M}^{\ell }_{y}$ Myℓ of minimal absent words of a wordyis equal to $\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$ M{y1,…,yk}ℓ for any decomposition ofyinto a collection of wordsy1, … ,yksuch that there is an overlap of length at leastℓ− 1 between any two consecutive words in the collection. This computation generally requiresΩ(n) space forn= |y| using any of the plenty available $\mathcal {O}(n)$ O(n) -time algorithms. This is because anΩ(n)-sized text index is constructed overywhich can be impractical for largen. We do the identical computation incrementally using output-sensitive space. This goal is reasonable when $\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| =o(n)$ ∥M{y1,…,yN}ℓ∥=o(n) , for allN∈ [1,k], where ∥S∥ denotes the sum of the lengths of words in setS. For instance, in the human genome,n≈ 3 × 109but $\| \mathrm {M}^{12}_{\{y_1,\ldots ,y_k\}}\| \approx 10^{6}$ ∥M{y1,…,yk}12∥≈106 . We consider a constant-sized alphabet for stating our results. We show thatall $\mathrm {M}^{\ell }_{y_{1}},\ldots ,\mathrm {M}^{\ell }_{\{y_1,\ldots ,y_k\}}$ My1ℓ,…,M{y1,…,yk}ℓ can be computed in $\mathcal {O}(kn+{\sum }^{k}_{N=1}\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| )$ O(kn+∑N=1k∥M{y1,…,yN}ℓ∥) total time using $\mathcal {O}(\textsc {MaxIn}+\textsc {MaxOut})$ O(MaxIn+MaxOut) space, where MaxIn is the length of the longest word in {y1, … ,yk} and $\textsc {MaxOut}=\max \limits \{\| \mathrm {M}^{\ell }_{\{y_1,\ldots ,y_N\}}\| :N\in [1,k]\}$ MaxOut=max{∥M{y1

A word x that is absent from a word y is called minimal if all its proper factors occur in y. Given a collection of k words y1, y2,...,ykover an alphabet Σ, we are asked to compute the set M(y1#...#yk)ℓof minimal absent words of length at most ℓ of word y=y1#y2#...#yk, #∉Σ. In data compression, this corresponds to computing the antidictionary of k documents. In bioinformatics, it corresponds to computing words that are absent from a genome of k chromosomes. This computation generally requires Ω(n) space for n=|y| using any of the plenty available O(n)-time algorithms. This is because an Ω(n)-sized text index is constructed over y which can be impractical for large n. We do the identical computation incrementally using output-sensitive space. This goal is reasonable when ||M(y1#...#yN)ℓ|| =o(n), for all N ϵ[1, k]. For instance, in the human genome, n ≈ 3 × 109but ||M (y1#...#yk)12|| ≈ 106. We consider a constant-sized alphabet for stating our results. We show that all M(y1)ℓ,...,M(y1#...#yk)ℓcan be computed in O(kn+ΣN=1k||M(y1#...#(yN)ℓ||) total time using O(MaxIn+MaxOut) space, where MaxIn is the length of the longest word in y1,...,ykand MaxOut=max{||M (y1)#...#(yN)ℓ||:N ϵ[1, k]. Proof-of-concept experimental results are also provided confirming our theoretical findings and justifying our contribution.

MOTIVATION: The biological significance of minimal absent words has been investigated in genomes of organisms from all domains of life. For instance, three minimal absent words of the human genome were found in Ebola virus genomes. There exists an O(n) -time and O(n) -space algorithm for computing all minimal absent words of a sequence of length n on a fixed-sized alphabet based on suffix arrays. A standard implementation of this algorithm, when applied to a large sequence of length n , requires more than 20 n bytes of RAM. Such memory requirements are a significant hurdle to the computation of minimal absent words in large datasets. RESULTS: We present emMAW, the first external-memory algorithm for computing minimal absent words. A free open-source implementation of our algorithm is made available. This allows for computation of minimal absent words on far bigger data sets than was previously possible. Our implementation requires less than 3 h on a standard workstation to process the full human genome when as little as 1 GB of RAM is made available. We stress that our implementation, despite making use of external memory, is fast; indeed, even on relatively smaller datasets when enough RAM is available to hold all necessary data structures, it is less than two times slower than state-of-the-art internal-memory implementations. AVAILABILITY AND IMPLEMENTATION: https://github.com/solonas13/maw (free software under the terms of the GNU GPL). CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

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 [Formula: see text]-time and [Formula: see text]-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 [Formula: see text]-time and [Formula: see text]-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 [Formula: see text]-time and [Formula: see text]-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.