title: Exact and heuristic methods for network completion for time-varying genetic networks.
abstract: Robustness in biological networks can be regarded as an important feature of living systems. A system maintains its functions against internal and external perturbations, leading to topological changes in the network with varying delays. To understand the flexibility of biological networks, we propose a novel approach to analyze time-dependent networks, based on the framework of network completion, which aims to make the minimum amount of modifications to a given network so that the resulting network is most consistent with the observed data. We have developed a novel network completion method for time-varying networks by extending our previous method for the completion of stationary networks. In particular, we introduce a double dynamic programming technique to identify change time points and required modifications. Although this extended method allows us to guarantee the optimality of the solution, this method has relatively low computational efficiency. In order to resolve this difficulty, we developed a heuristic method for speeding up the calculation of minimum least squares errors. We demonstrate the effectiveness of our proposed methods through computational experiments using synthetic data and real microarray gene expression data. The results indicate that our methods exhibit good performance in terms of completing and inferring gene association networks with time-varying structures.
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, Japan.
authors.forename: Natsu
authors.initials: N
authors.lastname: Nakajima
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, Japan.
authors.forename: Tatsuya
authors.identifier: 0000-0001-9763-797X
authors.initials: T
authors.lastname: Akutsu
mesh_terms: D001185:Artificial Intelligence; D019295:Computational Biology; D003198:Computer Simulation; D020869:Gene Expression Profiling; D053263:Gene Regulatory Networks; D006801:Humans
references.citation: BMC Syst Biol. 2010 Sep 22;4:130
references.pmid: 20860793
references.citation: Pac Symp Biocomput. 1998;:18-29
references.pmid: 9697168
references.citation: Nucleic Acids Res. 2010 Jan;38(Database issue):D355-60
references.pmid: 19880382
references.citation: Nature. 2008 May 1;453(7191):98-101
references.pmid: 18451861
references.citation: Science. 2002 Sep 27;297(5590):2270-5
references.pmid: 12351791
references.citation: Bioinformatics. 2012 Dec 15;28(24):3298-305
references.pmid: 23074260
references.citation: ScientificWorldJournal. 2012;2012:957620
references.pmid: 23213307
references.citation: Biosystems. 2009 Apr;96(1):86-103
references.pmid: 19150482
references.citation: Proc Natl Acad Sci U S A. 2009 Dec 29;106(52):22073-8
references.pmid: 20018705
references.citation: Bioinformatics. 2006 Oct 1;22(19):2413-20
references.pmid: 16864593
references.citation: J Comput Biol. 2000;7(3-4):601-20
references.pmid: 11108481
references.citation: J Bioinform Comput Biol. 2003 Jul;1(2):231-52
references.pmid: 15290771
references.citation: Bioinformatics. 2007 Jul 1;23(13):1623-30
references.pmid: 17463021
references.citation: Bioinformatics. 2000 Aug;16(8):727-34
references.pmid: 11099258
references.citation: Bioinformatics. 2000 Aug;16(8):707-26
references.pmid: 11099257
references.citation: IET Syst Biol. 2007 May;1(3):149-63
references.pmid: 17591174
references.citation: Bioinformatics. 2002 Feb;18(2):287-97
references.pmid: 11847076
references.citation: Proc IEEE Comput Syst Bioinform Conf. 2005;:289-98
references.pmid: 16447986
references.citation: EURASIP J Bioinform Syst Biol. 2009;:617281
references.pmid: 19551137
references.citation: Mol Biol Cell. 1998 Dec;9(12):3273-97
references.pmid: 9843569