Frequently, a set of conserved (common) 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
International Journal of Computers, Systems and Signals, Vol. 6, No. 2, 2005 3
SOME IMPLEMENTATION ISSUES OF HEURISTIC METHODS
FOR MOTIF EXTRACTION FROM DNA SEQUENCES
Liang Yang, Enli Huang and Vladimir B Bajic
Knowledge Extraction Lab, Institute for Infocomm Research, 21 Heng Mui Keng Terrace,
Singapore 119613
,
ABSTRACT
Frequently, a set of conserved (common) 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. We discuss some of the most crucial aspects of computer implementation of three heuristic algorithms which can be used in computational extraction of such conserved motifs from a set of unaligned DNA/RNA sequences. The algorithms included are tabu search, simulated annealing and a population-based genetic algorithm. A server with these algorithms implemented is available as a public web application free for academic and non-profit users at . This tool can be directly applied in determination of functional patterns in DNA and RNA.
Keywords: ab initio DNA motif discovery, heuristic methods, genetic algorithms, simulated annealing, tabu search.
1. INTRODUCTION
One of the most common problems in bioinformatics is alignment of biological sequences, either DNA/RNA or proteins. This is done for the reasons of finding parts of different biological sequences which share certain level of similarity, since such information is in a broad use in determining sequence functionality. Many efficient programs for local and global alignments are developed such as BLAST (Altschul et al, 1990), FASTA (Pearson and Lipman, 1988, Pearson, 1990), ClustalW (Higgins et al, 1994), etc. However, for the purpose of modeling particular groups of patterns which are common to a set of sequences, with the aim of using these models to search for the new members of the hypothetically functional group, these general alignment programs do not provide the most useful solutions, mainly due to the facts that they are based on far too many constraints imposed by the speed of program and due to the form in which they express the similarity between the sequences. Moreover, they are not very efficient in aligning short motifs, such as those usually representing transcriptional regulatory elements.
Many biological sequences which belong to a group of functionally related genes or proteins, usually contain a number of biologically active sequence patterns shared among some and sometimes all members of the functional group. A typical example represents promoters of a group of co-expressed genes which contain many common transcriptional regulatory elements which also share similar positional organization such as order and mutual distances (Werner, 1999). Determination of the best models of these common patterns is a great challenge.
There are several surveys (Brazma et al., 1998; Rigoutsos et al., 2000; Brejova et al., 2000) related to motif extraction problems. Several computer programs exist which can be used for this purpose such as MEME (Baily and Elkan, 1994), GibbsDNA (Lawrence et al, 1993), CONSESUS (Hetz and Stormo, 1999), AlignACE (Roth et al, 1998), TEIRESIAS (Rigoutsos and Floratos, 1998), SAM (Hughey and Krogh, 1998), SPLASH (Califano, 2000), Weeder Web (Pavesi et al, 2004) and probabilistic suffix trees (Berejano and Yona, 2001). Interesting to note, these programs produce mutually quite different results. This is not necessarily a bad thing as this may be useful for the users to make selections to suite
Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph ...The study of larger subgraphs highlights some striking patterns for various N...
Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph ...The study of larger subgraphs highlights some striking patterns for various N...
热门文档