2020/05/27 by Diego P. Rubert, Rubert, Diego P, Elói Araújo +7
Biochemistry, Genetics and Molecular Biology · #Bioinformatics and Genomic Networks #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.0 #FOS: Computer and information sciences #G.2.1 #G.3 #Gene Regulatory Network Analysis #Gene expression and cancer classification
paper · pdf · doi:10.48550/arxiv.2005.13634
openalex publication_date 2020/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
One of the most important concepts in biological network analysis is that of network motifs, which are patterns of interconnections that occur in a given network at a frequency higher than expected in a random network. In this work we are interested in searching and inferring network motifs in a class of biological networks that can be represented by vertex-colored graphs. We show the computational complexity for many problems related to colorful topological motifs and present efficient algorithms for special cases. We also present a probabilistic strategy to detect highly frequent motifs in vertex-colored graphs. Experiments on real data sets show that our algorithms are very competitive both in efficiency and in quality of the solutions.