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

• DOI: 10.1007/s00453-007-9008-7
• Publication Date: 2007-09-21T15:34:29Z
• Authors: Falk Hüffner; Sebastian Wernicke; Thomas Zichner
• Keywords: Color-coding; Theory of computation; Implementation

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.