On the Common Substring Alignment Problem

✍ Scribed by Gad M Landau; Michal Ziv-Ukelson

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 164 KB
• Volume: 41
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2001.1191

✦ Synopsis

The Common Substring Alignment Problem is defined as follows: Given a set of one or more strings S 1 S 2 S c and a target string T , Y is a common substring of all strings S i , that is, S i = B i YF i . The goal is to compute the similarity of all strings S i with T , without computing the part of Y again and again. Using the classical dynamic programming tables, each appearance of Y in a source string would require the computation of all the values in a dynamic programming table of size O n where is the size of Y . Here we describe an algorithm which is composed of an encoding stage and an alignment stage. During the first stage, a data structure is constructed which encodes the comparison of Y with T . Then, during the alignment stage, for each comparison of a source S i with T , the precompiled data structure is used to speed up the part of Y . We show how to reduce the O n alignment work, for each appearance of the common substring Y in a source string, to O n -at the cost of O n encoding work, which is executed only once.