title: A parallel algorithm for reverse engineering of biological networks.
abstract: Dynamic biological systems, such as gene regulatory networks (GRNs) and protein signaling networks, are often represented as systems of ordinary differential equations. Such equations can be utilized in reverse engineering these biological networks, specifically since identifying these networks is challenging due to the cost of the necessary experiments growing with at least the square of the size of the system. Moreover, the number of possible models, proportional to the number of directed graphs connecting nodes representing the variables in the system, suffers from combinatorial explosion as the size of the system grows. Therefore, exhaustive searches for systems of nontrivial complexity are not feasible. Here we describe a practical and scalable algorithm for determining candidate network interactions based on decomposing an N-dimensional system into N one-dimensional problems. The algorithm was tested on in silico networks based on known biological GRNs. The computational complexity of the network identification is shown to increase as N(2) while a parallel implementation achieves essentially linear speedup with the increasing number of processing cores. For each in silico network tested, the algorithm successfully predicts a candidate network that reproduces the network dynamics. This approach dramatically reduces the computational demand required for reverse engineering GRNs and produces a wealth of exploitable information in the process. Moreover, the candidate network topologies returned by the algorithm can be used to design future experiments aimed at gathering informative data capable of further resolving the true network topology.
authors.affiliation: Medical College of Wisconsin, 8701 Watertown Plank Rd., Milwaukee, USA.  beardda@gmail.com.
authors.forename: Jason N
authors.initials: JN
authors.lastname: Bazil
authors.forename: Feng
authors.initials: F
authors.lastname: Qi
authors.forename: Daniel A
authors.initials: DA
authors.lastname: Beard
mesh_terms: D000465:Algorithms; D000818:Animals; D003198:Computer Simulation; D005786:Gene Expression Regulation / Q000502:physiology*; D006801:Humans; D008954:Models, Biological; D025941:Protein Interaction Mapping / Q000379:methods*; D020543:Proteome / Q000378:metabolism*; D015398:Signal Transduction / Q000502:physiology*
chemical_list: D020543:Proteome
references.citation: Nat Biotechnol. 2005 Mar;23(3):377-83
references.pmid: 15765094
references.citation: Bioinformatics. 2004 Dec 12;20(18):3638-40
references.pmid: 15247099
references.citation: BMC Bioinformatics. 2009 May 20;10:155
references.pmid: 19457258
references.citation: Proc Natl Acad Sci U S A. 2010 Apr 6;107(14):6286-91
references.pmid: 20308593
references.citation: BMC Bioinformatics. 2006 Mar 20;7 Suppl 1:S7
references.pmid: 16723010
references.citation: Bioinformatics. 2009 Feb 15;25(4):490-6
references.pmid: 19136553
references.citation: J Biotechnol. 2009 Nov;144(3):190-203
references.pmid: 19631244
references.citation: J Biol Chem. 2001 Sep 28;276(39):36168-73
references.pmid: 11395518
references.citation: Proc Natl Acad Sci U S A. 2002 Apr 30;99(9):6163-8
references.pmid: 11983907
references.citation: Bioessays. 1998 May;20(5):433-40
references.pmid: 9670816
references.citation: Proc Natl Acad Sci U S A. 2003 May 13;100(10):5944-9
references.pmid: 12730377
references.citation: Mol Syst Biol. 2007;3:78
references.pmid: 17299415
references.citation: EURASIP J Bioinform Syst Biol. 2007;:79879
references.pmid: 18354736
references.citation: Phys Life Rev. 2005 Mar;2(1):65-88
references.pmid: 20416858
references.citation: Brief Bioinform. 2009 Jul;10(4):408-23
references.pmid: 19505889
references.citation: Science. 2003 Jul 4;301(5629):102-5
references.pmid: 12843395
references.citation: Biosystems. 2000 Feb;55(1-3):129-36
references.pmid: 10745116
references.citation: Bioinformatics. 2000 Aug;16(8):707-26
references.pmid: 11099257
references.citation: Ann N Y Acad Sci. 2007 Dec;1115:xi-xiv, 1-285
references.pmid: 18240416
references.citation: PLoS Biol. 2007 Jan;5(1):e8
references.pmid: 17214507
references.citation: Proc Natl Acad Sci U S A. 1998 Dec 8;95(25):14863-8
references.pmid: 9843981
references.citation: Nature. 2000 Oct 5;407(6804):651-4
references.pmid: 11034217
references.citation: Syst Biol (Stevenage). 2006 Jul;153(4):247-56
references.pmid: 16986626
references.citation: PLoS Comput Biol. 2009 Mar;5(3):e1000322
references.pmid: 19300515
references.citation: BMC Bioinformatics. 2007 Sep 27;8 Suppl 6:S5
references.pmid: 17903286
references.citation: J Comput Biol. 2009 Feb;16(2):229-39
references.pmid: 19183003
references.citation: Nat Rev Genet. 2001 Apr;2(4):268-79
references.pmid: 11283699
references.citation: Genome Res. 2004 Aug;14(8):1654-63
references.pmid: 15289483
references.citation: Proc Natl Acad Sci U S A. 2000 Oct 24;97(22):12182-6
references.pmid: 11027309
references.citation: Nat Rev Mol Cell Biol. 2008 Oct;9(10):770-80
references.pmid: 18797474
references.citation: BMC Syst Biol. 2010 Sep 28;4:132
references.pmid: 20920161