Efficient detection of unusual words

Area of Science:

• Bioinformatics
• Computational Biology
• Stringology

Background:

• Over- and underrepresented words in biological sequences are linked to various functions.
• Traditional anomaly detection methods exhaustively enumerate and individually analyze words.
• This can be computationally intensive and may miss complex patterns.

Purpose of the Study:

• To develop a global approach for detecting anomalous words using suffix tree annotations.
• To create an efficient preliminary filter for identifying suspicious words in sequences.
• To analyze sequence behavior under a simple probabilistic model.

Main Methods:

• Annotating suffix trees with statistical values (mean, variance, significance scores).
• Utilizing a probabilistic model for sequence generation.
• Embedding combinatorial string properties into statistical expressions for optimal computation.

Main Results:

• Achieved time-and-space optimal annotation of suffix trees for mean, variance, and significance.
• Computed expected value and variance for all substrings in O(n^2) worst-case and O(n log n) expected time/space.
• Identified candidate over/underrepresented words at internal suffix tree nodes, reducing search space to O(n).

Conclusions:

• The global suffix tree annotation method provides an efficient and accurate way to detect sequence anomalies.
• This approach significantly improves upon traditional methods by reducing computational complexity.
• Developed global detectors for favored/unfavored words in linear time and space.