Mathematical Foundations of Programming

Article # 16_2015

9 p.

PDF

submitted on 14th Dec 2014 displayed on website on 26th Feb 2015

Znamenskij S.V.
A model and algorithm for sequence alignment

The change detection problem is aimed at identifying common and different strings and usually has non-unique solutions. The identification of the best alignment is canonically based on finding a longest common subsequence (LCS) and is widely used for various purposes. However, many recent version control systems prefer alternative heuristic algorithms which not only are faster but usually produce better alignment than finding an LCS. Two basic shortcomings of known alignment algorithms are outlined in the paper:

(1) LCS sometimes mistakenly consist of short uninformative common strings;
(2) known alternative algorithms starts from a most informative common string identification which sometimes suppress identification of appropriately long sequence of slightly less informative common strings.

The sequence alignment problem is considered to be an abstract model for changes detection in collaborative text editing designed to minimize the probability of merge conflict. A new cost function is defined as the probability of intersection between detected changes and random string. It avoids both the mentioned shortcomings. The cubic algorithm is proposed.

Key words: similarity of strings, sequence alignment, software development, diff, LCS, edit distance, Levenshtein metric.

article citation

DOI

https://doi.org/10.25209/2079-3316-2015-6-1-189-197