首页> 外文期刊>Algorithmica >Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection
【24h】

Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection

机译:颜色编码的算法工程及其在信号通路检测中的应用

获取原文
获取原文并翻译 | 示例

摘要

Color-coding is a technique to design fixed-parameter algorithms for several NP-complete subgraph isomorphism problems. Somewhat surprisingly, not much work has so far been spent on the actual implementation of algorithms that are based on color-coding, despite the elegance of this technique and its wide range of applicability to practically important problems. This work gives various novel algorithmic improvements for color-coding, both from a worst-case perspective as well as under practical considerations. We apply the resulting implementation to the identification of signaling pathways in protein interaction networks, demonstrating that our improvements speed up the color-coding algorithm by orders of magnitude over previous implementations. This allows more complex and larger structures to be identified in reasonable time; many biologically relevant instances can even be solved in seconds where, previously, hours were required.
机译:颜色编码是一种用于为几个NP完全子图同构问题设计固定参数算法的技术。出乎意料的是,尽管这项技术非常优雅,并且对于实际重要的问题具有广泛的适用性,但是到目前为止,在基于颜色编码的算法的实际实现上并没有花费太多的工作。从最坏的情况以及实际考虑出发,这项工作为颜色编码提供了各种新颖的算法改进。我们将结果实现应用于蛋白质相互作用网络中的信号通路识别,表明我们的改进比以前的实现将颜色编码算法提高了几个数量级。这样可以在合理的时间内识别出更复杂,更大的结构。许多生物学相关的实例甚至可以在几秒钟内解决,而以前则需要数小时。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号