Optimal Algorithm for Finding DNA Motifs with Nucleotide Adjacent Dependency

Francis Y. L. Chin, Henry C. M. Leung, Man-Hung Siu, Siu-Ming YiuAPBC 2008

Abstract

Traditional DNA motif discovery often relies on the assumption of nucleotide independence, which fails to capture the biological reality of adjacent dependencies in binding sites. While complex models like Hidden Markov Models (HMMs) can account for these dependencies, they are computationally intensive and often lack optimality guarantees. This paper introduces DPS-Finder, a branch-and-bound algorithm utilizing a simplified Dependency Pattern Sets (DPS) representation. By constraining the model to a manageable number of wildcard positions, DPS-Finder achieves mathematical optimality in minutes, significantly outperforming heuristic and HMM-based approaches in both speed and accuracy.

Introduction

In bioinformatics, identifying "motifs"—recurring DNA patterns that serve as protein binding sites—is crucial for understanding gene regulation. Most existing tools represent these motifs as simple strings or Position Weight Matrices (PWMs). However, these models typically assume that the nucleotide at one position is independent of its neighbors.

Biological evidence suggests that "adjacent dependency" is common in transcription factor binding sites. While sophisticated models like HMMs can capture these relationships, they require vast amounts of training data and are computationally expensive. The authors propose a "Goldilocks" solution: the DPS model, which is complex enough to capture essential dependencies but simple enough to allow for efficient, optimal discovery.

Methodology: DPS Representation and DPS-Finder

The core of this research lies in two innovations: the DPS representation and the DPS-Finder algorithm.

Dependency Pattern Sets (DPS)

The DPS model is a refinement of the String-Pattern-String-Pattern (SPSP) model. It represents a motif as a sequence of pattern sets. To maintain computational feasibility, the authors restrict the model such that at most two positions are "wildcards"—regions containing multiple possible short sequences. This design choice reflects the biological observation that most binding sites are highly conserved, with variation concentrated in specific regions.

The DPS-Finder Algorithm

To find the motif with the lowest p-value (the "optimal" motif), the authors developed DPS-Finder. The algorithm leverages two primary techniques:

  1. $l$-factor Trees: A specialized suffix tree structure that organizes all possible motifs within the input sequences. This allows the algorithm to process overlapping substrings efficiently by shifting a search window.
  2. Branch-and-Bound Search: Since finding the optimal motif is NP-hard, the algorithm uses a branch-and-bound strategy to prune the search space. By calculating bounds on the potential p-value of a branch, the algorithm can skip large portions of the tree that cannot possibly contain the global optimum.
The $l$-factor tree structure used by DPS-Finder to navigate the motif search space efficiently.

Experimental Evaluation

The algorithm was tested using the Saccharomyces Cerevisiae Promoter Database (SCPD), focusing on 600 base-pair sequences upstream of genes regulated by specific yeast transcription factors.

Performance and Accuracy

DPS-Finder demonstrates significant advantages in both speed and discovery power:

  • Efficiency: The algorithm can identify a length-10 motif from 22 sequences (500bp each) in minutes, whereas HMM-based methods might require hours or days.
  • Optimality: Unlike heuristic tools like MEME or SPSP-Finder, which can get trapped in local optima, DPS-Finder guarantees finding the mathematically best motif within its model constraints. For example, in the MCM1 dataset, DPS-Finder successfully identified the true optimal motif where SPSP-Finder failed.
Comparison of motif discovery results across various transcription factors, showing DPS-Finder's ability to capture complex dependencies compared to other tools.

Discussion and Limitations

While DPS-Finder offers a powerful alternative to traditional methods, it has specific limitations. In experiments where the "Hamming distance" (the number of allowed mutations in a wildcard set) was restricted to 1, the algorithm missed motifs with higher variation, such as HAP2/3/4. Additionally, for motifs lacking a strong consensus sequence (e.g., SFF), traditional matrix-based models like MEME may still be more effective.

Future work involves extending the model to handle "local motif pairs" or non-adjacent dependencies, where nucleotides might influence positions further down the sequence.

Summary updated

BibTeX
@inproceedings{chin2008optimal,
  author = {Francis Y. L. Chin and Henry C. M. Leung and Man-Hung Siu and Siu-Ming Yiu},
  title = {{Optimal Algorithm for Finding DNA Motifs with Nucleotide Adjacent Dependency}},
  booktitle = {APBC},
  year = {2008},
}
Figure