Polynomial algorithms for the Maximal Pairing Problem: efficient phylogenetic targeting on arbitrary trees |
| |
Authors: | Christian Arnold " target="_blank">Peter F Stadler |
| |
Institution: | 1.Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics,University of Leipzig,Leipzig,Germany;2.Department of Human Evolutionary Biology,Harvard University,Cambridge,USA;3.Max Planck Institute for Mathematics in the Sciences,Leipzig,Germany;4.Fraunhofer Institute for Cell Therapy and Immunology,Leipzig,Germany;5.Santa Fe Institute,Santa Fe,USA;6.Institute for Theoretical Chemistry,University of Vienna,Wien,Austria |
| |
Abstract: | BackgroundThe 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 ω xy 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.ConclusionsThe 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, i.e., data collection with resource limitations. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|