Title :
Graphical approach for motif recognition in DNA sequences
Author :
Yang, Xiao ; Rajapakse, Jagath C.
Author_Institution :
Sch. of Comput. Eng., Nanyang Technol. Univ., Singapore
Abstract :
Several algorithms have been developed for motif recognition in the past few years, superior in some sense over others, yet not a single one was declared to be the "best". Some of the well recognized algorithms are based on heuristic methods, such as Gibbs sampling and expectation maximization, and enumeration methods, such as Oligo-analysis. However, the inability to solve the "Challenge Problem" in motif recognition showed the drawbacks of the existing heuristic and enumeration methods. Two new algorithms were developed to resolve this problem but still, they suffered from time and space expense and the problem of local optima. We proposed a new algorithm which can solve the challenge problem with better performance even in very long sequences by applying dynamic programming for path searching in a graph and scanning with the consensus sequence to eliminate faked motif instances.
Keywords :
DNA; biology computing; dynamic programming; graph theory; heuristic programming; sampling methods; DNA sequence; Gibbs sampling; Oligo-analysis; bioinformatics; dynamic programming; enumeration method; expectation maximization; graphical approach; heuristic method; motif recognition; Bioinformatics; Character recognition; DNA; Dynamic programming; Fungi; Genomics; Sampling methods; Senior members; Sequences; Testing;
Conference_Titel :
Computational Intelligence in Bioinformatics and Computational Biology, 2004. CIBCB '04. Proceedings of the 2004 IEEE Symposium on
Print_ISBN :
0-7803-8728-7
DOI :
10.1109/CIBCB.2004.1393947