joe at evolution.genetics.washington.edu (Joe Felsenstein) writes:
> Is "true" alignment done by backtracking in N dimensional space?
> If the sequences evolved on a tree, shouldn't one do "true" alignment
> the way David Sankoff proposed to do it in 1973, namely by
> jointly estimating the tree and the alignments along the tree?
>> If it is done that way the problems are very difficult but at least
> one does not ever do an N-dimensional dynamic programming algorithm.
In the end, the time complexity depends on the objective function you
use, but as a general statement, this is not true. If jointly
estimating the tree and the alignment while minimizing the amount of
evolution in the tree is the objective, in CS known as generalized
tree alignment, then there are no known exact algorithms that use less
than N-dim dynprog. Even in the case of aligning with respect to a
known tree, there are no known efficient exact algorithms. Se papers
by Tao Jiang and coworkers for more details, they have proved these
problems to be computationally hard.
Best regards,
Lars
--
Lars Arvestad Pharmacia Corp., Stockholm
