Optimal computation of overabundant words

DOI10.4230/LIPICS.WABI.2017.4MaRDI QIDQ5111793zbMATH OpenOpenAlexFDO

Authors Panagiotis Charalampopoulos, Jia Gao, Costas S. Iliopoulos, Manal Mohamed, Solon P. Pissis, Dimitris Polychronopoulos, Yannis Almirantis

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1705.03385

zbMATH Keywords

suffix treeDNA sequence analysisavoided wordsoverabundant words

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Computational methods for problems pertaining to biology (92-08)

Abstract: The observed frequency of the longest proper prefix, the longest proper suffix, and the longest infix of a word $w$ in a given sequence $x$ can be used for classifying $w$ as avoided or overabundant. The definitions used for the expectation and deviation of $w$ in this statistical model were described and biologically justified by Brendel et al. (J Biomol Struct Dyn 1986). We have very recently introduced a time-optimal algorithm for computing all avoided words of a given sequence over an integer alphabet (Algorithms Mol Biol 2017). In this article, we extend this study by presenting an $mathcalO(n)$-time and $mathcalO(n)$-space algorithm for computing all overabundant words in a sequence $x$ of length $n$ over an integer alphabet. Our main result is based on a new non-trivial combinatorial property of the suffix tree $mathcalT$ of $x$: the number of distinct factors of $x$ whose longest infix is the label of an explicit node of $mathcalT$ is no more than $3n-4$. We further show that the presented algorithm is time-optimal by proving that $mathcalO(n)$ is a tight upper bound for the number of overabundant words. Finally, we present experimental results, using both synthetic and real data, which justify the effectiveness and efficiency of our approach in practical terms.

Recommendations

• On overabundant words and their application to biological sequence analysis
• Computing maximal-exponent factors in an overlap-free word
• Optimal computation of avoided words
• Constructing antidictionaries of long texts in output-sensitive space
• Efficient computation of shortest absent words in a genomic sequence

Cites work

• Algorithms on Strings
• Assessing the Statistical Significance of Overrepresented Oligonucleotides
• Optimal computation of avoided words

Cited in

(3)

• The complexity of computing maximal word functions
• On overabundant words and their application to biological sequence analysis
• Optimal computation of avoided words

This page was built for publication: Optimal computation of overabundant words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111793)