4 ms·
FYI—sequence alignment algorithms are really just a specialized subset of diffing algorithms that take into account the properties of biological sequences. (For
by thanatosmin 7y ago
FYI—sequence alignment algorithms are really just a specialized subset of diffing algorithms that take into account the properties of biological sequences. (For example, certain edits are more or less likely to happen.)
https://en.wikipedia.org/wiki/Sequence_alignment https://en.wikipedia.org/wiki/Sequence_alignment
- glofish 7y agoI would say that perhaps diff is a special case of alignments, but not in reverse. Alignments differ from a "diff" because they are assigning a score to each operation (match, mismatch, gap). The "optimal" alignment only cares about maximizing the score, does not "care" about the objects that are aligned. If one chooses the scores incorrectly they could end up with optimal (relative to the score) alignments that visually seem completely "wrong". I can't see how one could tune a diff, to produce obviously "incorrect" output.
- thanatosmin 7y agoMaybe most correct is to say diff and seq alignments are specializations of some superset, given the specializations for both situations. Diff algorithms absolutely do assign a "score" to edits, just in a very simple way. For example, by playing with the Myers diff algorithm, you can get an edit distance of one where you simply rewrite the entire file, or a large edit distance but with the smallest edits possible.