Motif Counting

Overview

“In this article, we show how to apply the ‘color coding’ technique for counting non-induced occurrences of subgraph topologies in the form of trees and bounded treewidth subgraphs. Our algorithm can count all occurrences of motif G′ with k vertices in a network G with n vertices in time polynomial with n, provided k=O(log n).”

Contact info

Phuong Dao

Publication

Biomolecular Network Motif Counting and Discovery by Color Coding

Alon N, Dao P, Hajirasouliha I, Hormozdiari Fe, Sahinalp SC

Bioinformatics 2008 24: i241-i249
Presented at ISMB’08 (16th Annual International Conference Intelligent Systems for Molecular Biology), Toronto, Canada, July 19-23.
Journal link | PubMed ID: 18586721 |