Algorithms of Ancestral Gene Length Reconstruction

الملخص EN

Ancestral sequence reconstruction is a well-known problem in molecular evolution.

The problem presented in this study is inspired by sequence reconstruction, but instead of leaf-associated sequences we consider only their lengths.

We call this problem ancestral gene length reconstruction.

It is a problem of finding an optimal labeling which minimizes the total length’s sum of the edges, where both a tree and nonnegative integers associated with corresponding leaves of the tree are the input.

In this paper we give a linear algorithm to solve the problem on binary trees for the Manhattan cost function s(v,w)=|π(v)−π(w)|.