String Matching... String Matching Problems and Bioinformatics

some alphabet Σ = {a1... aK} and a pattern or query string P = p1... pm, m < n in the same alphabet, find all occurrences of P in S. ”find all occurrences ” = report all positions i1,..., ik such that sij... sij+m = P. Approximate String Matching.[4] Given a string S = s1s2... sn of charachters in some alphabet Σ = {a1... aK}, pattern or query string P = p1... pm, m < n in the same alphabet, a maximum error allowed k ∈ R, and a distance function d: Σ ∗ × Σ ∗ → R, find all such positions i in S, that for some j, d(si... sj, P) ≤ k. String matching in bioinformatics. Certain known nucleotide and/or amino acid sequences have properties known to biologists. E.g.,ATG is a string which must be present at the beginning of every protein (gene) a DNA sequence. A primer is a conserved DNA sequence used in the Polymerase Chain Reaction (PCR) to identify the location of the DNA sequence that will be amplified (amplification starts at the location immediately following the 3 ’ end primer, known as the forward primer). Finding if a DNA sequence contains a specific (candidate) primer is therefore paramount to the ability to run correct PCR. A conserved DNA sequence is a sequence of nucleotides in DNA, which is found in the DNA of multiple species and/or multiple strains (for bacteria/prokaryotes), or, in general, in all/almost all sequences in a specific collection. Some sequences are conserved precisely. However, a lot of sequences are conserved with some modifications. Finding such modified strings is an important process for map-ping DNA of a new organism, based on the known DNA of a related organism. For example, we know that genetic code is redundant. Consider the following sequence of nucleotides: GCTACTATTTTTCAT When read in forward frame 0, this sequence encodes the following sequence of amino acids: 1 ATIFH Because of redundancy of the genetic code, the following sequences of nu-cleotides will produce the same sequence of amino acids (lower case letters show differences with the original string)