ProMotE: an efficient algorithm for counting independent motifs in uncertain network topologies

Area of Science:

• Computational Biology
• Network Science
• Bioinformatics

Background:

• Identifying functional motifs in biological networks is crucial for understanding their roles.
• Detecting non-overlapping motif instances is computationally intensive.
• Biological interaction uncertainty complicates motif embedding detection.

Purpose of the Study:

• To develop a novel method for counting non-overlapping motif embeddings in probabilistic networks.
• To address the computational challenges of motif discovery in uncertain biological networks.
• To improve the scalability and accuracy of motif analysis in large-scale biological networks.

Main Methods:

• Introduced ProMotE (Probabilistic Motif Embedding), a novel algorithm.
• Utilized a polynomial model to quantify interaction uncertainty.
• Developed three strategies to enhance algorithm scalability for large networks.

Main Results:

• ProMotE demonstrated high accuracy and scalability on large networks, outperforming existing methods.
• The method successfully counts non-overlapping motif embeddings in probabilistic networks.
• Experiments confirmed the method's ability to run in practical timeframes.

Conclusions:

• ProMotE offers an accurate and efficient solution for motif discovery in probabilistic biological networks.
• The method aids in uncovering key functional characteristics of networks, including those related to cancer and degenerative diseases.
• ProMotE overcomes limitations of existing methods in handling large and uncertain biological networks.