• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Algorithms in Bioinformatics(WABI 2004); 20040917-21; Bergen(NO) >A Polynomial-Time Algorithm for the Matching of Crossing Contact-Map Patterns
【24h】

A Polynomial-Time Algorithm for the Matching of Crossing Contact-Map Patterns

机译：交叉联系图模式匹配的多项式时间算法

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

摘要

Contact maps are a model to capture the core information in the structure of biological molecules, e.g., proteins. A contact map consists of an ordered set S of elements (representing a protein's sequence of amino acids), and a set A of element pairs of S, called arcs (representing amino acids which are closely neighbored in the structure). Given two contact maps (S, A) and (S_p, A_p) with |A| ≥ |A_p|, the CONTACT MAP PATTERN MATCHING (CMPM) problem asks whether the "pattern" (S_p,A_p) "occurs" in (S, A), i.e., informally stated, whether there is a subset of |A_p| arcs in A whose arc structure coincides with A_p. CMPM captures the biological question of finding structural motifs in protein structures. In general, CMPM is NP-hard. In this paper, we show that CMPM is solvable in O(|A|~6|A_p|~2) time when the pattern is {<, ()}-structured, i.e., when each two arcs in the pattern are disjoint or crossing. Our algorithm extends to other closely related models. In particular, it answers an open question raised by Vialette that, rephrased in terms of contact maps, asked whether CMPM for {<, ()}-structured patterns is NP-hard or solvable in polynomial time. Our result stands in sharp contrast to the NP-hardness of closely related problems. We provide experimental results which show that contact maps derived from real protein structures can be processed efficiently.
机译：接触图是在生物分子例如蛋白质的结构中捕获核心信息的模型。接触图由元素的有序集合S（代表蛋白质的氨基酸序列）和元素对S的集合A（称为弧）组成（称为弧）（代表在结构中紧密相邻的氨基酸）。给定两个具有| A |的联系图（S，A）和（S_p，A_p） ≥| A_p |，则“接触式地图模式匹配（CMPM）”问题询问（S，A）中是否“出现”了“模式”（S_p，A_p），即非正式地指出是否存在| A_p |的子集。 A中的弧，其弧结构与A_p一致。 CMPM捕获了在蛋白质结构中发现结构基序的生物学问题。通常，CMPM是NP硬的。在本文中，我们表明，当图案为{<，（）}结构时，即图案中的每两个弧不相交或相交时，CMPM可以在O（| A |〜6 | A_p |〜2）时间内求解。穿越。我们的算法扩展到其他紧密相关的模型。尤其是，它回答了Vialette提出的一个开放性问题，该问题用联系方式表述，询问用于{<，（）}结构的模式的CMPM在多项式时间内是NP难解还是可解。我们的结果与密切相关问题的NP硬度形成鲜明对比。我们提供的实验结果表明，可以有效地处理源自真实蛋白质结构的接触图。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号