Identification of Distinguishing Motifs

Motivation:

Motif identification for sequences has many important applications in biological studies, e.g., diagnostic probe design, locating binding sites and regulatory signals, and potential drug target identification. There are two versions.

1

Single Group:

Given a group of

n

sequences, find a length-

l

motif that appears in each of the given sequences and those occurrences of the motif are

similar

.

1

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

.

Here the occurrences of the motif in the given sequences have errors. Currently, most of existing programs can only handle the case of single group. Moreover, it is very difficult to use edit distance (allowing indels and replacements) for motif detection.

Results:

(1) We propose a randomized algorithm for the one group problem that can handle indels in the occurrences of the motif. (2) We give an algorithm for the two groups problem. (3) Extensive simulations have been done to evaluate the algorithms.