{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T06:04:16Z","timestamp":1740809056526,"version":"3.38.0"},"reference-count":10,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2003,5,1]],"date-time":"2003-05-01T00:00:00Z","timestamp":1051747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2003,5]]},"abstract":"<jats:p> With the recent DNA-microarray technology, it is possible to measure the expression levels of thousands of genes simultaneously in the same experiment. A genetic network is a model that describes how the expression level of each gene is affected by the expression levels of other genes in the network. In this paper we explore the use of parallel computers to infer genetic network architectures in gene expression analysis. Given the results of an experiment with n genes and m measures over time ( m [UNKNOWN] n), we consider the problem of finding a subset of genes ( k genes, where k [UNKNOWN] n) that explain the expression level of a given target gene under study. We consider the coarse-grained multicomputer (CGM) model, with p processors. We first present a sequential approximation algorithm of O( m<jats:sup>4<\/jats:sup> n) time and O( m<jats:sup>2<\/jats:sup> n) space. The main result is a new parallel approximation algorithm that determines the k genes in O( m<jats:sup>4<\/jats:sup> n\/p) local computing time plus O( k) communication rounds, and with space requirement of O( m<jats:sup>2<\/jats:sup> n\/p). The p factor in the parallel time and space complexities indicates a good parallelization. To our knowledge there are no CGM algorithms for the problem considered in this paper. We also show promising experimental results on a Beowulf machine. As will be shown in our experiments, we observe very promising speedups results, especially in the cases where the number of genes studied exceeds 4000. Notice that even with current microarray technology, microchips with around 15,000 spots are already possible. The proposed parallel method constitutes thus an excellent example of application of high-performance computing in this important field. <\/jats:p>","DOI":"10.1177\/1094342003017002006","type":"journal-article","created":{"date-parts":[[2003,6,25]],"date-time":"2003-06-25T22:04:01Z","timestamp":1056578641000},"page":"163-172","source":"Crossref","is-referenced-by-count":4,"title":["A Parallel Solution to Infer Genetic Network Architectures in Gene Expression Analysis"],"prefix":"10.1177","volume":"17","author":[{"given":"D. P.","family":"Ruchkys","sequence":"first","affiliation":[]},{"given":"S. W.","family":"Song","sequence":"additional","affiliation":[{"name":"UNIVERSIDADE DE S\u00c3O PAULO, INSTITUTO DE MATEM\u00c1TICA                        E ESTAT\u00cdSTICA, DEPARTAMENTO DE C\u00ceENCIA DA                        COMPUTA\u00c7\u00c3O, 05508-090 S\u00c3O PAULO, SP, BRAZIL"}]}],"member":"179","published-online":{"date-parts":[[2003,5,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"J. Barrera, E. R. Dougherty, M. D. Gubitoso, and N. S. T. Hirata. Modeling temporal morphological systems via lattice dynamical systems. In Electronic Imaging at SPIE Photonics. SPIE , 2001, pp. 248-259.","DOI":"10.1117\/12.424981"},{"key":"atypb2","unstructured":"F. Dehne. Coarse grained parallel algorithms . 2000. Algorithmica, 24(3\/4): 173-176 ."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"F. Dehne, A. Fabri, and A. Rau-Chaplin. Scalable parallel geometric algorithms for coarse grained multicomputers . In Proc. ACM 9th Annual Computational Geometry, 1993, pp. 298-307 .","DOI":"10.1145\/160985.161154"},{"key":"atypb4","unstructured":"D'haeseleer, P., Liang, S., and Somogyi. Gene expression data analysis and modeling. Tutorial notes from Pacific Symposium on Biocomputing, 1999."},{"key":"atypb5","unstructured":"Garey, M.R. and Johnson, D.S. 1999. Computers and intractability - A guide to the theory of NP-completeness. W.H. Freeman, 21th edition."},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"Hochbaum, D.S., editor. 1997. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company .","DOI":"10.1145\/261342.571216"},{"key":"atypb7","unstructured":"Ideker, T.E., Thorsson, V., and Karp, R.M. 2000. Discovery of regulatory interactions through perturbation: inference and experimental design. Pacific Symposium on Biocomputing, pp. 302-313 ."},{"key":"atypb8","unstructured":"Jha, S., Sheyner, O., and Wing, J.M. 2002. Minimization and reliability analyses of attack graphs. IEEE Symposium on Security and Privacy."},{"key":"atypb9","unstructured":"Liang, S., Fuhrman, S., and Somogyi, R. 1998. Reveal, a general reverse engineering algorithm for inference of genetic network architectures. Pacific Symposium on Biocomputing, pp. 18-29 ."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"Valiant, L. 1990. A bridging model for parallel computation. Communication of the ACM, 33(8): 103-111 .","DOI":"10.1145\/79173.79181"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342003017002006","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342003017002006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T00:32:20Z","timestamp":1740789140000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342003017002006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,5]]},"references-count":10,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,5]]}},"alternative-id":["10.1177\/1094342003017002006"],"URL":"https:\/\/doi.org\/10.1177\/1094342003017002006","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"type":"print","value":"1094-3420"},{"type":"electronic","value":"1741-2846"}],"subject":[],"published":{"date-parts":[[2003,5]]}}}