Identification of Distinguishing Motifs

Top

1. Introduction

Motif identification for DNA sequences has many important applications in biological studies, e.g., diagnostic probe design, locating binding sites and regulatory signals, and potential drug target identification (Dopazo, Rodriguez, Saiz, & Sobrino, 1993; Lucas, Busch, Mossinger, & Thompson, 1991; Proutski & Holme, 1996). The most general problem is as follows:

• Two Groups: Given two groups of sequences B and G, find a length-l (distinguishing) motif that appears in every sequence in B and does not appear in anywhere of the sequences in G.

The motif we want to find is called the distinguishing motif that can differentiate the two groups. If no error is allowed, the problem is easy. However, in practice, the occurrence of the motif in each of the given sequences has errors (mutations and indels). The problem becomes extremely hard when errors appear. Many mathematic models have been proposed.

The following definition was first stated in (Lanctot, Li, Ma, Wang, & Zhang, 1999).

• Distinguishing substring selection: given a set B = {s₁, s_2,…, s_n1} of n₁ (bad) strings of length at least l, and a set G = { g₁,g₂, …, g_n2} of n₂ (good) strings of length at least l, the problem is to find a string s of length l such that for each string s_i∈B there exists a length-l substring t_i of s_i with d_H(s, t_i)≤ d_b and for any length-l substring u_i of g_i∈ G, d_H(s, u_i)≥ d_g. Here d_b and d_g are two parameters, called the radius of the two groups. We want d_b to be small and d_g to be large. d_H(,) represents the Hamming distance between two strings.

When indels are allowed in the occurrences of the motif, the problem is called the distinguishing subsequence selection problem, where the input is the same as the previous problem and the objective here is to find a string s of length l such that for each string s_i ∈ B there exists a substring t_i of s_i with d(s, t_i) ≤ d_b and for any substring u_i of g_i ∈ G, d(s, u_i) ≥ dg. Here d(,) represents the edit distance.

A special case, where only one group of sequences is involved is as follows:

• Single Group: Given a group of n given sequences, find a motif that appears in each of the given sequences and those occurrences of the motif are similar.

There are several ways to define the similarity of the motif occurrences, e.g., the consensus score, general consensus score and SP-score (Hertz & Stormo, 1995; Li, Ma, & Wang, 1999). Here we use the following mathematical definitions.

• The Closest Substring Problem: Given n sequences {s₁, s₂, . . ., s_n}, each is of length m (m ≥ l), the problem is to find a center string s of length l and a substring t_i of length l in s_i such that

  

is minimized, where d_H (,) is the Hamming distance between the two strings of the same length.