...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Bioinformatics and Computational Biology >HEURISTIC SEARCH IN CONSTRAINED BIPARTITE MATCHING WITH APPLICATIONS TO PROTEIN NMR BACKBONE RESONANCE ASSIGNMENT
【24h】

HEURISTIC SEARCH IN CONSTRAINED BIPARTITE MATCHING WITH APPLICATIONS TO PROTEIN NMR BACKBONE RESONANCE ASSIGNMENT

机译：双约束匹配中的启发式搜索及其在蛋白质NMR骨干共振分配中的应用

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The constrained bipartite matching (CBM) problem is a variant of the classical bipartite matching problem that has been well studied in the Combinatorial Optimization community. The input to CBM is an edge-weighted complete bipartite graph in which there are a same number of vertices on both sides and vertices on one side are sequentially ordered while vertices on the other side are partitioned and connected into disjoint directed paths. In a feasible matching, a path must be mapped to consecutive vertices on the other side. The optimization goal is to find a maximum or a minimum weight perfect matching. Such an optimization problem has its applications to scheduling and protein Nuclear Magnetic Resonance peak assignment. It has been shown to be NP-hard and MAX SNP-hard if the perfectness requirement is dropped. In this paper, more results on the inapproximability are presented and IDA*, a memory efficient variant of the well known A* search algorithm, is utilized to solve the problem. Accordingly, search heuristics and a set of heuristic evaluation functions are developed to assist the search, whose effectiveness is demonstrated by a simulation study using real protein NMR backbone resonance assignment instances.
机译：约束二分匹配（CBM）问题是经典二分匹配问题的变体，该问题已在组合优化社区中进行了深入研究。 CBM的输入是一个边缘加权的完整二部图，其中在两侧都有相同数量的顶点，并且一侧的顶点被顺序排序，而另一侧的顶点被划分并连接成不相交的有向路径。在可行的匹配中，必须将路径映射到另一侧的连续顶点。优化目标是找到最大或最小权重完美匹配。这种优化问题已应用于调度和蛋白质核磁共振峰分配。如果降低了完美性要求，则证明它是NP-hard和MAX SNP-hard。在本文中，给出了关于不可逼近的更多结果，IDA *是众所周知的A *搜索算法的一种内存高效变体，用于解决该问题。因此，开发了搜索启发式方法和一组启发式评估功能来辅助搜索，其有效性通过使用真实蛋白质NMR主链共振分配实例的模拟研究得到证明。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号