License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2017.4
URN: urn:nbn:de:0030-drops-76468
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7646/
Almirantis, Yannis ;
Charalampopoulos, Panagiotis ;
Gao, Jia ;
Iliopoulos, Costas S. ;
Mohamed, Manal ;
Pissis, Solon P. ;
Polychronopoulos, Dimitris
Optimal Computation of Overabundant Words
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 O(n)-time and O(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 T of x: the number of distinct factors of x whose longest infix is the label of an explicit node of T is no more than 3n-4. We further show that the presented algorithm is time-optimal by proving that O(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.
BibTeX - Entry
@InProceedings{almirantis_et_al:LIPIcs:2017:7646,
author = {Yannis Almirantis and Panagiotis Charalampopoulos and Jia Gao and Costas S. Iliopoulos and Manal Mohamed and Solon P. Pissis and Dimitris Polychronopoulos},
title = {{Optimal Computation of Overabundant Words}},
booktitle = {17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
pages = {4:1--4:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-050-7},
ISSN = {1868-8969},
year = {2017},
volume = {88},
editor = {Russell Schwartz and Knut Reinert},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7646},
URN = {urn:nbn:de:0030-drops-76468},
doi = {10.4230/LIPIcs.WABI.2017.4},
annote = {Keywords: overabundant words, avoided words, suffix tree, DNA sequence analysis}
}
|
Keywords: |
|
overabundant words, avoided words, suffix tree, DNA sequence analysis |
|
Collection: |
|
17th International Workshop on Algorithms in Bioinformatics (WABI 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
11.08.2017 |
