Efficient algorithms for the discovery of gapped factors.

Area of Science:

• Bioinformatics and Computational Biology
• Genomics
• Sequence Analysis

Background:

• Discovering frequent patterns is crucial in bioinformatics and computational biology.
• Gapped factors, pairs of words co-occurring within a specific distance, are important in DNA and protein sequence analysis.
• Existing algorithms lack comprehensive handling of various distance definitions for gapped factors.

Purpose of the Study:

• To develop efficient algorithms and tools for extracting frequently co-occurring word pairs within a defined proximity in biological sequences.
• To address the limitations of existing methods in comprehensively defining and measuring the distance between word pairs.
• To enable the discovery of gapped factors across various distance metrics.

Main Methods:

• Efficient algorithms combining pattern maximality and score monotonicity properties.
• Reduced explicit weighing of word pairs by leveraging algorithmic properties.
• Development of tools for comprehensive extraction of gapped factors.

Main Results:

• Algorithms achieve O(n2) or O(n3) complexity for exhaustive discovery, a significant improvement over potential Θ(n4) complexity.
• Successfully applied the approach to discover spaced dyads in DNA sequences.
• The method efficiently identifies word pairs co-occurring surprisingly often in close proximity.

Conclusions:

• The developed method is effective and substantially faster than exhaustive enumeration for biological datasets.
• Software implementing the approach is freely available for academic users.
• The findings advance the field of pattern discovery in sequence analysis.