Discovering topological motifs using a compact notation.

Area of Science:

• Graph Theory
• Computational Biology
• Network Science

Background:

• Graph topology discovery is crucial for bioinformatics and network studies.
• The subgraph isomorphism problem, classically used for this, is NP-Complete.
• Output size explosion due to graph isomorphisms hinders practical application.

Purpose of the Study:

• To develop an exact and efficient method for discovering topological motifs in graphs.
• To address the combinatorial explosion of output size caused by isomorphisms.
• To adapt the concept of maximality from string processing to graph analysis.

Main Methods:

• A three-step approach applying graph maximality.
• Utilizing "compact location lists" to implicitly represent subgraph occurrences.
• Developing an algorithm linear in the size of the compact list output.

Main Results:

• A method that completely and exactly solves the topological motif discovery problem.
• Significant reduction in output size using compact location lists without information loss.
• An algorithm with linear time complexity relative to the encoded output size.

Conclusions:

• The proposed method offers an exact and efficient solution for graph topology discovery.
• Compact location lists effectively manage combinatorial complexity in graph isomorphism problems.
• This approach enhances the feasibility of large-scale network and bioinformatics analyses.