Title :
Extending Pattern Branching to Handle Challenging Instances
Author :
Davila, Jorge ; Rajasekaran, Sanguthevar
Author_Institution :
Dept. of Comput. Sci. & Eng., Connecticut Univ., Storrs, CT
Abstract :
We consider the planted motif search problem, a problem that arises from the need to find transcription factor-binding sites in genomic information. One of the fastest non-exact algorithms that solves this problem is pattern branching [10], however this algorithm fails to solve challenging instances such as (15, 5) in most cases. In this paper we discuss a simple extension to this algorithm and an implementation of it that allows us to tackle challenging instances such as (15, 5) and (17, 6) with accuracy close to 100%
Keywords :
biological techniques; biology computing; genetics; search problems; genomic information; instances handling; nonexact algorithms; pattern branching; planted motif search problem; transcription factor-binding sites; Bioinformatics; Computer science; Genomics; Polynomials; Search problems; Voting;
Conference_Titel :
BioInformatics and BioEngineering, 2006. BIBE 2006. Sixth IEEE Symposium on
Conference_Location :
Arlington, VA
Print_ISBN :
0-7695-2727-2
DOI :
10.1109/BIBE.2006.253317
