More Web Proxy on the site http://driver.im/

article

An Intelligent Two-Stage Evolutionary Algorithm for Dynamic Pathway Identification From Gene Expression Profiles

Authors:

Chih-Hung Hsieh,

Hui-Ling HuangAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 4, Issue 4

Pages 648 - 704

https://doi.org/10.1109/tcbb.2007.1051

Published: 01 October 2007 Publication History

Abstract

From gene expression profiles, it is desirable to rebuild cellular dynamic regulation networks to discover more delicate and substantial functions in molecular biology, biochemistry, bioengineering and pharmaceutics. S-system model is suitable to characterize biochemical network systems and capable to analyze the regulatory system dynamics. However, inference of an S-system model of N-gene genetic networks has 2N(N+1) parameters in a set of non-linear differential equations to be optimized. This paper proposes an intelligent two-stage evolutionary algorithm (iTEA) to efficiently infer the S-system models of genetic networks from time-series data of gene expression. To cope with curse of dimensionality, the proposed algorithm consists of two stages where each uses a divide-and-conquer strategy. The optimization problem is first decomposed into N subproblems having 2(N+1) parameters each. At the first stage, each subproblem is solved using a novel intelligent genetic algorithm (IGA) with intelligent crossover based on orthogonal experimental design (OED). At the second stage, the obtained N solutions to the N subproblems are combined and refined using an OED-based simulated annealing algorithm for handling noisy gene expression profiles. The effectiveness of iTEA is evaluated using simulated expression patterns with and without noise running on a single-processor PC. It is shown that 1) IGA is efficient enough to solve subproblems; 2) IGA is significantly superior to the existing method SPXGA; and 3) iTEA performs well in inferring S-system models for dynamic pathway identification.

References

[1]

D.J. Lockhart and E.A. Winzeler, “Genomics, Gene Expression and DNA Arrays,” Nature, vol. 405, no. 15, pp. 827-836, June 2000.

[2]

P. Brazhnik, A. de la Fuente, and P. Mendes, “Gene Networks: How to Put the Function in Genomics,” Trends in Biotechnology, vol. 20, no. 11, pp. 467-472, 2002.

[3]

T. Akutsu, S. Miyano, and S. Kuhara, “Algorithms for Identifying Boolean Networks and Related Biological Networks Based on Matrix Multiplication and Fingerprint Function,” J. Computational Biology, vol. 7, no. 3, pp. 331-343, 2000.

[4]

T. Akutsu, S. Miyano, and S. Kuhura, “Identification of Genetic Networks from a Small Number of Gene Expression Patterns under the Boolean Network Model,” Proc. Pacific Symp. Biocomputing, pp. 17-28, 1999.

[5]

S. Liang, S. Fuhrman, and R. Somogyi, “REVEAL, a General Reverse Engineering Algorithm for Inference of Genetic Network Architectures,” Proc. Pacific Symp. Biocomputing, vol. 3, pp. 18-29, 1998.

[6]

N. Friedman, M. Linial, I. Nachman, and D. Pe'er, “Using Bayesian Networks to Analyze Expression Data,” J. Computational Biology, vol. 7, no. 3, pp. 601-620, 2000.

[7]

D. Husmeier, “Sensitivity and Specificity of Inferring Genetic Regulatory Interactions from Microarray Experiments with Dynamic Bayesian Networks,” Bioinformatics, vol. 19, pp. 2271-2282, 2003.

[8]

J. Yu, V.A. Smith, P.P. Wang, A.J. Hartemink, and E.D. Jarvis, “Advances to Bayesian Network Inference for Generating Causal Networks from Observational Biological Data,” Bioinformatics, vol. 20, pp. 3594-3603, 2004.

Digital Library

[9]

M. Zou and S.D. Conzen, “A New Dynamic Bayesian Network (DBN) Approach for Identifying Gene Regulatory Networks from Time Course Microarray Data,” Bioinformatics, vol. 21, no. 1, pp.71-79, 2005.

Digital Library

[10]

S. Kikuchi, D. Tominaga, M. Arita, K. Takahashi, and M. Tomita, “Dynamic Modeling of Genetic Networks Using Genetic Algorithm and S-System,” Bioinformatics, vol. 19, pp. 643-650, 2003.

[11]

S. Kimura, M. Hatakeyama, and A. Konagaya, “Inference of S-System Models of Genetic Networks from Noisy Time-Series Data,” Chem-Bio Informatics J., vol. 4, no. 1, pp. 1-14, 2004.

[12]

S. Kimura, K. Ide, A. Kashihara, M. Kano, M. Hatakeyama, R. Masui, N. Nakagawa, S. Yokoyama, S. Kuramitsu, and A. Konagaya, “Inference of S-System Models of Genetic Networks Using a Cooperative Coevolutionary Algorithm,” Bioinformatics, vol. 21, pp. 1154-1163, 2005.

Digital Library

[13]

Y. Maki, T. Ueda, M. Okamoto, N. Uematsu, K. Inamura, K. Uchida, Y. Takahashi, and Y. Eguchi, “Inference of Genetic Network Using the Expression Profile Time Course Data of Mouse P19 Cells,” Genome Informatics, vol. 13, pp. 382-383, 2002.

[14]

R. Morishita, H. Imade, I. Ono, N. Ono, and M. Okamoto, “Finding Multiple Solutions Based on an Evolutionary Algorithm for Inference of Genetic Networks by S-System,” Proc. Congress Evolutionary Computation, vol. 1, pp. 615-622, 2003.

[15]

C. Seatzu, “A Fitting Based Method for Parameter Estimation in S-Systems,” Dynamic Systems and Applications, vol. 9, pp. 77-98, 2000.

[16]

D. Tominaga, N. Koga, and M. Okamoto, “Efficient Numerical Optimization Algorithm Based on Genetic Algorithm for Inverse Problem,” Proc. Genetic and Evolutionary Computation Conf., pp.251-258, 2000.

[17]

K.-Y. Tsai and F.-S. Wang, “Evolutionary Optimization with Data Collocation for Reverse Engineering of Biological Networks,” Bioinformatics, vol. 21, pp. 1180-1188, 2005.

Digital Library

[18]

E.O. Voit and J. Almeida, “Decoupling Dynamical Systems for Pathway Identification from Metabolic Profiles,” Bioinformatics, vol. 20, pp. 1670-1681, 2004.

Digital Library

[19]

A. Sorribas, S. Samitier, E.I. Canela, and M. Cascante, “Metabolic Pathway Characterization from Transient-Response Data Obtained In-Situ-Parameter-Estimation in S-System Models,” J.Theoretical Biology, vol. 162, pp. 81-102, 1993.

[20]

C.G. Moles, P. Mendes, and J.R. Banga, “Parameter Estimation in Biochemical Pathways: A Comparison of Global Optimization Methods,” Genome Research, vol. 13, pp. 2467-2474, 2003.

[21]

D. Tominaga and P. Horton, “Inference of Scale-Free Networks from Gene Expression Time Series,” J. Bioinformatics and Computational Biology, vol. 4, no. 2, pp. 503-514, Jan. 2006.

[22]

S.-Y. Ho, L.-S. Shu, and J.-H. Chen, “Intelligent Evolutionary Algorithms for Large Parameter Optimization Problems,” IEEE Trans. Evolutionary Computation, vol. 8, no. 6, pp. 522-541, Dec. 2004.

Digital Library

[23]

T.P. Bagchi, Taguchi Methods Explained: Practical Steps to Robust Design. Prentice Hall, 1993.

[24]

A.S. Hedayat, N.J.A. Sloane, and J. Stufken, Orthogonal Arrays: Theory and Applications. Springer, 1999.

[25]

S.-J. Ho, S.-Y. Ho, and L.-S. Shu, “OSA: Orthogonal Simulated Annealing Algorithm and Its Application to Designing Mixed H-2/H-Infinity Optimal Controllers,” IEEE Trans. Systems, Man, and Cybernetics-Part A: Systems and Humans, vol. 34, no. 5, pp. 588-600, Sept. 2004.

Digital Library

[26]

S.-J. Ho, L.-S. Shu, and S.-Y. Ho, “Optimizing Fuzzy Neural Networks for Tuning PID Controllers Using an Orthogonal Simulated Annealing Algorithm OSA,” IEEE Trans. Fuzzy Systems, vol. 14, no. 3, pp. 421-434, June 2006.

Digital Library

[27]

D. Thieffry, A.M. Huerta, E. Perez-Rueda, and J. Collado-Vides, “From Specific Gene Regulation to Genomic Networks: A Global Analysis of Transcriptional Regulation in Escherichia Coli,” BioEssays, vol. 20, pp. 433-440, 1998.

[28]

H. Szu and R. Hartley, “Fast Simulated Annealing,” Physics Letters, vol. 122, pp. 157-162, 1987.

[29]

S. Wei, T.W. Sun, and R.D. Wesel, “Quasi-Convexity and Optimal Binary Fusion for Distributed Detection with Identical Sensors in Generalized Gaussian Noise,” IEEE Trans. Information Theory, vol. 47, no. 1, pp. 446-450, 2001.

Digital Library

Cited By

Wu SWu C(2015)A bio-inspired optimization for inferring interactive networksExpert Systems with Applications: An International Journal10.1016/j.eswa.2014.11.03942:6(3253-3267)Online publication date: 15-Apr-2015
https://dl.acm.org/doi/10.1016/j.eswa.2014.11.039
Shatnawi MZaki N(2015)Inter-domain linker prediction using amino acid compositional indexComputational Biology and Chemistry10.1016/j.compbiolchem.2015.01.00655:C(23-30)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1016/j.compbiolchem.2015.01.006
Wu SWu C(2014)Seeding-inspired chemotaxis genetic algorithm for the inference of biological systemsComputational Biology and Chemistry10.1016/j.compbiolchem.2014.09.00353:PB(292-307)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.compbiolchem.2014.09.003
Show More Cited By

Index Terms

An Intelligent Two-Stage Evolutionary Algorithm for Dynamic Pathway Identification From Gene Expression Profiles

Recommendations

Inferring large scale genetic networks with S-system model
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

Gene regulatory network (GRN) reconstruction from high-throughput microarray data is an important problem in systems biology. The S-System model, a differential equation based approach, is among the mainstream approaches for modeling GRNs. It has the ...
Integrated pathway-based transcription regulation network mining and visualization based on gene expression profiles

Display Omitted An integrated pathway-oriented method is proposed for analyzing transcription regulation networks from gene expression data.The method currently is based on KEGG pathway definitions but is flexible to other pathway models.This improves ...
Evolutionary Biclustering Algorithm of Gene Expression Data
DEXA '12: Proceedings of the 2012 23rd International Workshop on Database and Expert Systems Applications

Microarrays represent a new technology for measuring expression levels of several genes under various biological conditions generating multiple data. These data can be analyzed by using biclustering method which aims to extract a maximum number of genes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 4, Issue 4

October 2007

192 pages

ISSN:1545-5963

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 October 2007

Published in TCBB Volume 4, Issue 4

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
287
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu SWu C(2015)A bio-inspired optimization for inferring interactive networksExpert Systems with Applications: An International Journal10.1016/j.eswa.2014.11.03942:6(3253-3267)Online publication date: 15-Apr-2015
https://dl.acm.org/doi/10.1016/j.eswa.2014.11.039
Shatnawi MZaki N(2015)Inter-domain linker prediction using amino acid compositional indexComputational Biology and Chemistry10.1016/j.compbiolchem.2015.01.00655:C(23-30)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1016/j.compbiolchem.2015.01.006
Wu SWu C(2014)Seeding-inspired chemotaxis genetic algorithm for the inference of biological systemsComputational Biology and Chemistry10.1016/j.compbiolchem.2014.09.00353:PB(292-307)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.compbiolchem.2014.09.003
Kentzoglanakis KPoole M(2012)A Swarm Intelligence Framework for Reconstructing Gene NetworksIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2011.879:2(358-371)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1109/TCBB.2011.87
Sun JGaribaldi JHodgman C(2012)Parameter Estimation Using Metaheuristics in Systems BiologyIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2011.639:1(185-202)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1109/TCBB.2011.63
Liu LWu FZhang W(2012)Inference of Biological S-System Using the Separable Estimation Method and the Genetic AlgorithmIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2011.1269:4(955-965)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1109/TCBB.2011.126
Lee WHsiao Y(2012)Inferring gene regulatory networks using a hybrid GA-PSO approach with numerical constraints and network decompositionInformation Sciences: an International Journal10.1016/j.ins.2011.11.020188(80-99)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1016/j.ins.2011.11.020
Liu LWu FZhang W(2012)Reverse engineering of gene regulatory networks from biological dataWiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery10.1002/widm.10682:5(365-385)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1002/widm.1068
Mitra SDas RHayashi Y(2011)Genetic Networks and Soft ComputingIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2009.398:1(94-107)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1109/TCBB.2009.39
Yeh WLin WHsieh TLiu S(2011)Feasible prediction in S-system models of genetic networksExpert Systems with Applications: An International Journal10.1016/j.eswa.2010.06.04238:1(193-197)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1016/j.eswa.2010.06.042
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents