High-performance exact algorithms for motif search

Document Type

Article

Publication Date

10-2005

Publication Title

Journal of Clinical Monitoring and Computing

Volume

19

Issue

4-5

First page number:

319

Last page number:

328

Abstract

OBJECTIVE:

The human genome project has resulted in the generation of voluminous biological data. Novel computational techniques are called for to extract useful information from this data. One such technique is that of finding patterns that are repeated over many sequences (and possibly over many species). In this paper we study the problem of identifying meaningful patterns (i.e., motifs) from biological data, the motif search problem.

METHODS:

The general version of the motif search problem is NP-hard. Numerous algorithms have been proposed in the literature to solve this problem. Many of these algorithms fall under the category of heuristics. We concentrate on exact algorithms in this paper. In particular, we concentrate on two different versions of the motif search problem and offer exact algorithms for them.

RESULTS:

In this paper we present algorithms for two versions of the motif search problem. All of our algorithms are elegant and use only such simple data structures as arrays. For the first version of the problem described as Problem 1 in the paper, we present a simple sorting based algorithm, SMS (Simple Motif Search). This algorithm has been coded and experimental results have been obtained. For the second version of the problem (described in the paper as Problem 2), we present two different algorithms--a deterministic algorithm (called DMS) and a randomized algorithm (Monte Carlo algorithm). We also show how these algorithms can be parallelized.

CONCLUSIONS:

All the algorithms proposed in this paper are improvements over existing algorithms for these versions of motif search in biological sequence data. The algorithms presented have the potential of performing well in practice.

Keywords

Algorithms; Amino Acid Motifs; Computational biology; Human genome; Humans; Information Storage And Retrieval; Information storage and retrieval systems; Men; Motif Search; Pattern Recognition; Automated; Pattern recognition systems; Short Sequence Motifs; Women

Disciplines

Computer Sciences | Genetics and Genomics | Neurosciences

Language

English

Find It

UNLV article access

Search your library

Share

COinS