Algorithm Engineering for Color-Coding to Facilitate Signaling Pathway Detection
Algorithm Engineering for Color-Coding to Facilitate Signaling Pathway Detection
复制标题
颜色编码算法工程以促进信号通路检测
DOI：
10.1142/9781860947995_0030
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
T. Zichner
中科院分区：
文献类型：
--
作者：
Falk Hüffner;S. Wernicke;T. Zichner
为了识别线性信号通路，Scott等人[RECOMB，2005]最近提出从蛋白质相互作用网络中提取具有高相互作用概率的通路。他们使用了一种称为颜色编码的算法技术来解决这个NP难题;他们的实现能够在几个小时内找到长度高达10个蛋白质的生物学上有意义的途径。在这项工作中，我们给出了各种新的算法改进的颜色编码，无论是从最坏的情况下的角度来看，以及在实际的考虑。酵母和果蝇的相互作用网络的实验，以及结构上可比的随机网络的测试床证明了该算法的数量级的加速。这允许在合理的时间内识别更复杂和更大的结构;甚至可以在几秒钟内找到长度高达13个蛋白质的路径，从而允许对候选路径进行交互式探索和评估。
To identify linear signaling pathways, Scott et al. [RECOMB, 2005] recently proposed to extract paths with high interaction probabilities from protein interaction networks. They used an algorithmic technique known as color-coding to solve this NP-hard problem; their implementation is capable of finding biologically meaningful pathways of length up to 10 proteins within hours. In this work, we give various novel algorithmic improvements for color-coding, both from a worst-case perspective as well as under practical considerations. Experiments on the interaction networks of yeast and fruit fly as well as a testbed of structurally comparable random networks demonstrate a speedup of the algorithm by orders of magnitude. This allows more complex and larger structures to be identified in reasonable time; finding paths of length up to 13 proteins can even be done in seconds and thus allows for an interactive exploration and evaluation of pathway candidates.