Motif discovery in biological network using expansion tree.

Area of Science:

• Computational Biology
• Network Science
• Bioinformatics

Background:

• Biological systems are often represented as complex networks, such as protein interaction and gene regulation networks.
• Network motifs, statistically significant recurrent patterns, are considered fundamental building blocks of these complex networks.
• Identifying network motifs is crucial for understanding network modularity, large-scale structure, and for applications like protein function annotation, but remains computationally challenging due to graph isomorphism problems.

Purpose of the Study:

• To propose an efficient and scalable algorithm for network motif discovery.
• To address the computational challenges associated with identifying network motifs in large biological networks.
• To develop a motif-centric algorithm that avoids computationally expensive graph isomorphism checks.

Main Methods:

• A novel algorithm, Motif Discovery based on Expansion Tree (MODET), is proposed, utilizing a pattern growth approach.
• Each node in the expansion tree represents a unique, non-isomorphic pattern.
• Embeddings for child nodes are derived from parent nodes via vertex and edge addition, bypassing graph isomorphism checks.

Main Results:

• The MODET algorithm demonstrates high computational efficiency, with specific time complexities for vertex and edge addition processes.
• Testing on a Protein-Protein Interaction (PPI) network from the MINT database confirmed its performance.
• The algorithm's computational efficiency surpasses that of many existing network motif discovery methods.

Conclusions:

• MODET offers an efficient and scalable solution for network motif discovery in biological networks.
• The algorithm's design effectively overcomes the computational hurdles posed by graph isomorphism.
• MODET represents a significant advancement in the analysis of complex biological networks.