title: Algorithms of ancestral gene length reconstruction.
abstract: 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)|.
authors.affiliation: Department of Evolutionary and Environmental Biology, Institute of Evolution, University of Haifa, 199 Aba-Hushi Avenue, Mount Carmel, Haifa 3498838, Israel ; Institute of Evolution, University of Haifa, Mount Carmel., Haifa 39105, Israel.
authors.forename: Alexander
authors.initials: A
authors.lastname: Bolshoy
authors.affiliation: The Tauber Bioinformatics Center, University of Haifa, 199 Aba-Hushi Avenue, Mount Carmel, Haifa 3498838, Israel.
authors.forename: Valery M
authors.initials: VM
authors.lastname: Kirzhner
mesh_terms: D000465:Algorithms; D017124:Conserved Sequence / Q000235:genetics*; D019143:Evolution, Molecular; D008962:Models, Theoretical; D017422:Sequence Analysis, DNA