Extending Pattern Branching to Handle Challenging Instances
Jaime I Davila · 2006
We consider the planted motif search problem, a problem that arises from the need to find transcription factorbinding 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%.