Identifying Reversing Substitutions

Problem

For a rooted tree T whose internal nodes are labeled with genetic strings, our goal is to identify reversing substitutions in T. Assuming that all the strings of T have the same length, a reversing substitution is defined formally as two parent-child string pairs (s,t) and (v,w) along with a position index i, where:

there is a path in T from s down to w;
s[i]=w[i]≠v[i]=t[i]; and
if u is on the path connecting t to v, then t[i]=u[i].
In other words, the third condition demands that a reversing substitution must be contiguous: no other substitutions can appear between the initial and reversing substitution.

Given: A rooted binary tree T with labeled nodes in Newick format, followed by a collection of at most 100 DNA strings in FASTA format whose labels correspond to the labels of T. We will assume that the DNA strings have the same length, which does not exceed 400 bp).

Return: A list of all reversing substitutions in T (in any order), with each substitution encoded by the following three items:

the name of the species in which the symbol is first changed, followed by the name of the species in which it changes back to its original state
the position in the string at which the reversing substitution occurs; and
the reversing substitution in the form original_symbol->substituted_symbol->reverted_symbol.