Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2017 Mar 14;18(Suppl 2):209.
doi: 10.1186/s12864-017-3495-y.

Active module identification in intracellular networks using a memetic algorithm with a new binary decoding scheme

Dong Li  1 , Zhisong Pan  2 , Guyu Hu  2 , Zexuan Zhu  3 , Shan He  4
Affiliations

Active module identification in intracellular networks using a memetic algorithm with a new binary decoding scheme

Dong Li et al. BMC Genomics. .

Abstract

Background: Active modules are connected regions in biological network which show significant changes in expression over particular conditions. The identification of such modules is important since it may reveal the regulatory and signaling mechanisms that associate with a given cellular response.

Results: In this paper, we propose a novel active module identification algorithm based on a memetic algorithm. We propose a novel encoding/decoding scheme to ensure the connectedness of the identified active modules. Based on the scheme, we also design and incorporate a local search operator into the memetic algorithm to improve its performance.

Conclusion: The effectiveness of proposed algorithm is validated on both small and large protein interaction networks.

Keywords: Connectedness; Memetic algorithm; Module identification; Module size.

PubMed Disclaimer

Figures

Fig. 1
Fig. 1
Modules identified by GA on simulated data. The red nodes are not connected though they are supposed to be
Fig. 2
Fig. 2
Modules identified by modified GA with proposed encoding scheme on the same simulated data as in Fig. 1. The red nodes are connected
Fig. 3
Fig. 3
Statistical comparison of performance w.r.t module scores from three algorithms: genetic algorithm, memetic algorithm and simulated annealing
Fig. 4
Fig. 4
Convergence rate comparison of three algorithms: genetic algorithm, memetic algorithm and simulated annealing from one trail. MA is the first to reaches the stable status
Fig. 5
Fig. 5
The first identified module plotted by STRING, where edges represent both known interactions including curated databases and experimentally determined and predicted interactions such as gene neighborhood and gene co-occurrence
Fig. 6
Fig. 6
The relatively small module plotted by GeneMANIA, where most of edges are co-expression links according to previous studies
See this image and copyright information in PMC

References

    1. Wang Y, Eddy JA, Price ND. Reconstruction of genome-scale metabolic models for 126 human tissues using mcadre. BMC Syst Biol. 2012;6(1):153. doi: 10.1186/1752-0509-6-153. - DOI - PMC - PubMed
    1. Girvan M, Newman ME. Community structure in social and biological networks. Proc Natl Acad Sci. 2002;99(12):7821–6. doi: 10.1073/pnas.122653799. - DOI - PMC - PubMed
    1. Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U. Network motifs: simple building blocks of complex networks. Science. 2002;298(5594):824–7. doi: 10.1126/science.298.5594.824. - DOI - PubMed
    1. Barabási AL, Gulbahce N, Loscalzo J. Network medicine: a network-based approach to human disease. Nat Rev Genet. 2011;12(1):56–68. doi: 10.1038/nrg2918. - DOI - PMC - PubMed
    1. Ideker T, Ozier O, Schwikowski B, Siegel AF. Discovering regulatory and signalling circuits in molecular interaction networks. Bioinformatics. 2002;18(suppl 1):233–40. doi: 10.1093/bioinformatics/18.suppl_1.S233. - DOI - PubMed

Publication types

LinkOut - more resources