Algorithm for Position Specific Approximate Pattern matching to determine Transcription Factor Binding Sites

There are many approximate pattern matching algorithms proposed in the literature. They mainly focus on solving the k mismatch problem which �nd all occurrences of a short pattern in a long text string with at most k mismatches. But these mismatches can be anywhere in the pattern. In many cases it is essential to find the approximate pattern varying only in specified locations. Finding Transcription Factor Binding Site along the DNA is an application of such type of fuzzy pattern matching. Transcription factors (TFs) are proteins that bind to the DNA molecule to control the expression of their target genes. TFs have a DNA-binding domain that recognizes a short specific DNA sequence called transcription factor binding site (TFBS) and bind to DNA. Every transcription factor is able to bind not only to a single DNA sequence but to a variety of DNA sequences that share a core structure. Binding motif for a TF is an approximate pattern in which variation can occur at specific positions in the pattern. The paper proposes an approximate pattern matching algorithm that allows position specific variation in the pattern. The algorithm can be used to locate the potential Transcription Factor Binding Sites along the DNA