tailieunhanh - Báo cáo sinh học: "Polynomial algorithms for the Maximal Pairing Problem: efficient phylogenetic targeting on arbitrary trees"

Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: Polynomial algorithms for the Maximal Pairing Problem: efficient phylogenetic targeting on arbitrary trees. | Arnold and Stadler Algorithms for Molecular Biology 2010 5 25 http content 5 1 25 AMR ALGORITHMS FOR MOLECULAR BIOLOGY RESEARCH Open Access Polynomial algorithms for the Maximal Pairing Problem efficient phylogenetic targeting on arbitrary trees Christian Arnold1 2 Peter F Stadler1 3 4 5 6 Abstract Background The Maximal Pairing Problem MPP is the prototype of a class of combinatorial optimization problems that are of considerable interest in bioinformatics Given an arbitrary phylogenetic tree T and weights rnxy for the paths between any two pairs of leaves x y what is the collection of edge-disjoint paths between pairs of leaves that maximizes the total weight Special cases of the MPP for binary trees and equal weights have been described previously algorithms to solve the general MPP are still missing however. Results We describe a relatively simple dynamic programming algorithm for the special case of binary trees. We then show that the general case of multifurcating trees can be treated by interleaving solutions to certain auxiliary Maximum Weighted Matching problems with an extension of this dynamic programming approach resulting in an overall polynomial-time solution of complexity 0 n4 log n . the number n of leaves. The source code of a C implementation can be obtained under the GNU Public License from http Software Targeting. For binary trees we furthermore discuss several constrained variants of the MPP as well as a partition function approach to the probabilistic version of the MPP. Conclusions The algorithms introduced here make it possible to solve the MPP also for large trees with high-degree vertices. This has practical relevance in the field of comparative phylogenetics and for example in the context of phylogenetic targeting . data collection with resource limitations. Background Comparisons among species are fundamental to elucidate evolutionary history. In evolutionary biology for example they can be