A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements; e.g. “acef” is a subsequence of “abcdef.” Consider the problem of finding the longest common subsequence of two sequences – this is a task versioning systems like git or cvs often solve. Show that this is a special case of the sequence alignment problem. Then, give a polynomial-time algorithm for finding the longest subsequence common to three sequences. Analyze its running time and argue why it is correct.