Application of heuristic methods in finding patterns common to groups of biological sequences.

Abstract

Frequently, a set of conserved motifs in a group of functionally related biological sequences (DNA/RNA or proteins) has a specific biological function. Determination of compact groups of these common patterns is a prerequisite for their efficient modeling. However, this problem is a great challenge because of its exponentially increased computational time. For this project, we provide three heuristic algorithms, which can be used in computational extraction of such conserved motifs from a set of unaligned DNA sequences. They are based on Simulated Annealing, Tabu Search and Genetic Algorithm. The algorithms and the most crucial aspects of the implementation are discussed in detail. We also present the comparison results with the other well known algorithms on the benchmark datasets used in a recent evaluation study.