Program Systems: Theory and Applications, 2015, Volume 6, Issue 1, Pages 189–197
This article is cited in 3 scientific papers (total in 3 papers)
Mathematical Foundations of Programming
A model and algorithm for sequence alignment
S. V. Znamenskij
Program Systems Institute of RAS
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 also usually produce better alignment than finding an LCS.
Two basic shortcomings of known alignment algorithms are outlined in the paper:
The sequence alignment problem is considered to be an abstract model for change detection in collaborative text editing designed to minimize the probability of merge conflict.
A new cost function is defined as the probability of overlap between detected changes and a random string.
This optimization avoids both shortcomings mentioned above. The simple cubic algorithm is proposed.
- even when the length of the longest common substring is close to that
of the LCS, the latter may consist of a great number of short
- known alternative algorithms start with identifying the most informative common string,
which sometimes omits from consideration common subsequence
containing arbitrarily many aligned substrings of similar quality.
Key words and phrases:
similarity of strings, sequence alignment, software development, diff, LCS, edit distance, Levenshtein metric.
PDF file (1151 kB)
S. V. Znamenskij, “A model and algorithm for sequence alignment”, Program Systems: Theory and Applications, 6:1 (2015), 189–197
Citation in format AMSBIB
\paper A model and algorithm for sequence alignment
\jour Program Systems: Theory and Applications
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
Sergej V. Znamenskij, “Simple essential improvements to the ROUGE-W algorithm”, Zhurn. SFU. Ser. Matem. i fiz., 8:4 (2015), 497–501
S. V. Znamenskij, “Stable assessment of the quality of similarity algorithms
of character strings and their normalizations”, Programmnye sistemy: teoriya i prilozheniya, 9:4 (2018), 561–578
S. V. Znamenskii, “Ustoichivaya otsenka kachestva algoritmov skhodstva simvolnykh strok i ikh normalizatsii”, Programmnye sistemy: teoriya i prilozheniya, 9:4 (2018), 579–596
|Number of views:|