Disjoint motif discovery in biological network using pattern join method. Issue 5 (4th July 2019)

• Record Type: Journal Article
• Authors: Patra, Sabyasachi; Mohapatra, Anjali
• Is Part Of: IET systems biology. Volume 13:Issue 5(2019)
• Page Start: 213
• Page End: 224
• Publication Date: 2019-07-04
• Subjects: graph theory -- bioinformatics -- network theory (graphs) -- complex networks -- pattern classification -- microorganisms -- proteins -- computational complexity -- diseases -- molecular biophysics -- genetics; Saccharomyces cerevisiae -- Escherichia coli -- pattern join method -- disjoint motif discovery -- protein interaction network -- transcription regulatory network -- target network -- network motif -- biological network; Systems biology -- Periodicals; Cell physiology -- Periodicals; Biological systems -- Mathematical models -- Periodicals; Genetics -- Mathematical models -- Periodicals; Computational biology -- Periodicals; 573
• DOI: 10.1049/iet-syb.2019.0008
• Languages: English
• ISSNs: 1751-8849

Abstract

Abstract : The biological network plays a key role in protein function annotation, protein superfamily classification, disease diagnosis, etc. These networks exhibit global properties like small‐world property, power‐law degree distribution, hierarchical modularity, robustness, etc. Along with these, the biological network also possesses some local properties like clustering and network motif. Network motifs are recurrent and statistically over‐represented subgraphs in a target network. Operation of a biological network is controlled by these motifs, and they are responsible for many biological applications. Discovery of network motifs is a computationally hard problem and involves a subgraph isomorphism check which is NP‐complete. In recent years, researchers have developed various tools and algorithms to detect network motifs efficiently. However, it is still a challenging task to discover the network motif within a practical time bound for the large motif. In this study, an efficient pattern‐join based algorithm is proposed to discover network motif in biological networks. The performance of the proposed algorithm is evaluated on the transcription regulatory network of Escherichia coli and the protein interaction network of Saccharomyces cerevisiae . The running time of the proposed algorithm outperforms most of the existing algorithms to discover large motifs.