On avoided words, absent words, and their application to biological sequence analysis

Area of Science:

• Computational Biology
• Bioinformatics
• Genomic Sequence Analysis

Background:

• Avoided words are identified by the deviation of their observed frequency from expected frequencies within a sequence.
• This concept is valuable in DNA linguistic analysis for characterizing word significance based on context.
• Calculating avoided words naively is computationally intensive, especially for longer sequences or larger alphabets.

Purpose of the Study:

• To develop efficient algorithms for computing avoided words in biological sequences.
• To address the computational challenges associated with identifying avoided words of specific lengths and all lengths.

Main Methods:

• A linear-time and linear-space algorithm is proposed for computing all avoided words of a specific length k.
• A time-optimal algorithm is presented for finding all avoided words of any length over an integer alphabet.
• The study provides combinatorial results and an implementation of the developed algorithms.

Main Results:

• An efficient algorithm computes all k-length avoided words in O(n) time and space.
• A time-optimal algorithm finds all avoided words (any length) in O(n) time.
• Experimental results demonstrate the algorithm's efficiency and applicability in biological sequence analysis.

Conclusions:

• The systematic search for avoided words is highly beneficial for biological sequence analysis.
• Linear-time and linear-space algorithms have been developed for computing avoided words of length k and all lengths.
• The research contributes combinatorial insights into avoided and absent words in sequences.