A branch-and-cut approach to physical mapping of chromosomes by unique end-probes
A branch-and-cut approach to physical mapping of chromosomes by unique end-probes
复制标题
DOI：
10.1089/cmb.1997.4.433
复制
发表时间：
1997-12-01
影响因子：
1.7
通讯作者：
Reinelt, G
中科院分区：
文献类型：
--
作者：
Christof, T;Junger, M;Reinelt, G
计算生物学中的一个基本问题是在存在误差的情况下，从独特探针和染色体片段克隆之间的杂交实验构建染色体的物理图谱，Alizadeh，Karp，Weisser和Zweig（Micromica 13：1/2，52-76，1995）首先考虑了该问题的最大似然模型，其等价于找到使误差的加权和最小化的探针排序，并开发了几种有效的算法。我们表明，通过利用克隆的末端探针的信息，这个模型可以被公式化为加权介数问题，这提供了显着的优势，允许整数线性规划和分支切割算法的发达工具，以承担物理映射，使我们第一次解决小映射实例，即使在存在高误差的情况下，最优，我们还表明，通过结合许多小的重叠介数问题的最优解，可以有效地从较大的实例中筛选错误，并将编辑后的实例作为汉明距离旅行商问题解决到最优，这提出了一种新的方法，一个介数-旅行商混合，用于构建物理地图。
A fundamental problem in computational biology is the construction of physical maps of chromosomes from hybridization experiments between unique probes and clones of chromosome fragments in the presence of error, Alizadeh, Karp, Weisser and Zweig (Algorithmica 13:1/2, 52-76, 1995) first considered a maximum-likelihood model of the problem that is equivalent to finding an ordering of the probes that minimizes a weighted sum of errors and developed several effective heuristics. We show that by exploiting information about the end-probes of clones, this model can be formulated as a Weighted Betweenness Problem, This affords the significant advantage of allowing the well-developed tools of integer linear-programming and branch-and-cut algorithms to be brought to bear on physical mapping, enabling us for the first time to solve small mapping instances to optimality even in the presence of high error, We also show that by combining the optimal solution of many small overlapping Betweenness Problems, one can effectively screen errors from larger instances and solve the edited instance to optimality as a Hamming-Distance Traveling Salesman Problem, This suggests a new approach, a Betweenness-Traveling Salesman hybrid, for constructing physical maps.