Journal of Data Mining in Genomics & Proteomics

Algorithm of ancestral gene lengths reconstruction

2^nd International Conference on Big Data Analysis and Data Mining

November 30-December 01, 2015 San Antonio, USA

Alexander Bolshoy

University of Haifa, Israel
University of British Columbia, Canada

Posters-Accepted Abstracts: J Data Mining Genomics Proteomics

Abstract:

Ancestral sequence reconstruction (ASR) is a well-known problem in molecular evolution. The problem of the parsimonial reconstruction of ancestral states for the given tree with the given states of its leaves (the most parsimonious assignment of the labels of internal nodes for a fixed tree topology) is a well studied problem. The problem presented in this study is inspired by ASR but it is based on simpler model. Instead of considering leaf-associated sequences we take into account only their lengths. The problem may be called as ancestral gene length reconstruction (AGLR). In other words, AGLR is a problem of finding an optimal labeling which minimizes the total 'length' sum of the edges, the minimum sum problem where both a tree and non-negative integers associated with corresponding leaves of the tree are the input. In this study we contribute two dynamic-programming based algorithms: a pseudo-polynomial algorithm to solve the max sum problem on trees for a monotonically increasing cost function, and a linear algorithm to solve max sum problem on binary trees for the Manhattan cost function s(v,w) = |Ï?(v)-Ï?(w)|.

Biography :

Alexander Bolshoy is an Associated Professor in the Department of Evolutionary and Environmental Biology, and a member of the Institute of Evolution at the University of Haifa, Israel. He completed his Ph.D. from the Weizmann Institute of Science in Computational Structural Biology in 1993. He has been a major player in the field of DNA Linguistics and in the field of DNA curvature and bendability since the 1990-ies. He is the author of the book and many scientific articles, and has been serving as an editorial board member of several bioinformatics journals.