1
$\begingroup$

optimal lifted alignment - is a dynamic programming algorithm. Its input is a tree $T$ with $k$ strings assigned to its leaf nodes (their length is $n$).

The algorithm then assigns strings to the internal nodes s.t. the sum of distance (global alignment distance) on all the edges would be minimal, under the constraint that the string assigned to each node is one of the strings of its immediate children (hence the name "lifted").

The algorithm first computes distances $D$ between all pairs $O(k^2n^2)$. For each leaf node $v$ assigned $S_v$ we initialize: $d(S, v) = 0 | S = S_v$ and $d(S, v) = \infty | S \neq S_v$.

We then traverse post-order and for each internal node $v$, for each string $S$ assigned to one of its leaf descendants (all strings in its subtree) does $d(v,S) = \sum{\min(D(S,T) + d(w,T))}$ where $w$ are $v$'s immediate children. Overall = $O(k^2n^2 + k^3)$.

I've been told its possible to improve the complexity to $O(k^2n^2 + k^2)$ but I can't see how? Would appreciate any hint.

$\endgroup$
  • $\begingroup$ I don't understand your definition of $d(v, s)$ -- is $s$ the same as $S$? Also don't you mean "for each string $S$ assigned to one of its immediate children"? (If you chose a string for a node that was not one of the strings assigned to its immediate children, this would be an invalid solution, would it not?) $\endgroup$ – j_random_hacker Nov 30 '16 at 11:55
  • $\begingroup$ I don't quite understand your algorithm and its running time analysis, and the link you provided is in somewhat bad shape. Please explain more clearly the problem, the algorithm, and the runtime analysis. $\endgroup$ – Yuval Filmus Nov 30 '16 at 11:57
  • $\begingroup$ (Side note: If all strings have length $n$, it suggests you may want Hamming distance, which (unlike, say, Levenshtein distance) can be computed in linear time, shaving a factor of $n$.) $\endgroup$ – j_random_hacker Nov 30 '16 at 11:59
  • $\begingroup$ @YuvalFilmus, j_random_hacker - tried to clarify all your (justified) questions in the description. Please revise. $\endgroup$ – ihadanny Nov 30 '16 at 21:29
2
$\begingroup$

Consider a node $x$ with children $x_1,\ldots,x_d$, and denote by $N(v)$ the number of leaves in the subtree $T(v)$ rooted at $v$. We can implement the processing of $x$ as follows:

  • Go over $1 \leq i \leq d$:
    • Choose a leaf $f_i \in T(x_i)$ as the label of $x$ and $x_i$.
    • For all $j \neq i$, choose the leaf $f_j \in T(x_j)$ that minimizes $D(f_i,f_j) + d(x_j,f_j)$.
    • Store $d(x,f_i) = \sum_{j \neq i} [D(f_i,f_j) + d(x_j,f_j)]$.

The processing time of $x$ is proportional to $$ \sum_{i=1}^d N(x_i) \times \sum_{j \neq i} N(x_j) = \left(\sum_{i=1}^d N(x_i)\right)^2 - \sum_{i=1}^d N(x_i)^2 = N(x)^2 - \sum_{i=1}^d N(x_i)^2. $$ Summing over all nodes $x$ up to the root $r$, we see that the total processing time is proportional to $N(r)^2 = k^2$.

$\endgroup$
  • $\begingroup$ Wow, that's great! Can you share how did you come up with the intuition to this direction? $\endgroup$ – ihadanny Nov 30 '16 at 22:16
  • 1
    $\begingroup$ I guessed that the actual running time is $O(k^2)$, I wrote the recurrence relation, and this popped out. $\endgroup$ – Yuval Filmus Nov 30 '16 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.