Reconstructing the pathways of a cellular system from genome-scale signals by using matrix and tensor computations

doi:10.1073/pnas.0509033102

Reconstructing the pathways of a cellular system from genome-scale signals by using matrix and tensor computations

Orly Alter*,‡ and
Gene H. Golub‡,§

^*Department of Biomedical Engineering and Institute for Cellular and Molecular Biology, University of Texas, Austin, TX 78712; and ^§Scientific Computing and Computational Mathematics Program and Department of Computer Science, Stanford University, Stanford, CA 94305

Contributed by Gene H. Golub, October 17, 2005

Abstract

We describe the use of the matrix eigenvalue decomposition (EVD) and pseudoinverse projection and a tensor higher-order EVD (HOEVD) in reconstructing the pathways that compose a cellular system from genome-scale nondirectional networks of correlations among the genes of the system. The EVD formulates a genes × genes network as a linear superposition of genes × genes decorrelated and decoupled rank-1 subnetworks, which can be associated with functionally independent pathways. The integrative pseudoinverse projection of a network computed from a “data” signal onto a designated “basis” signal approximates the network as a linear superposition of only the subnetworks that are common to both signals and simulates observation of only the pathways that are manifest in both experiments. We define a comparative HOEVD that formulates a series of networks as linear superpositions of decorrelated rank-1 subnetworks and the rank-2 couplings among these subnetworks, which can be associated with independent pathways and the transitions among them common to all networks in the series or exclusive to a subset of the networks. Boolean functions of the discretized subnetworks and couplings highlight differential, i.e., pathway-dependent, relations among genes. We illustrate the EVD, pseudoinverse projection, and HOEVD of genome-scale networks with analyses of yeast DNA microarray data.

Footnotes

↵ ‡ To whom correspondence may be addressed. E-mail: orlyal{at}mail.utexas.edu or golub{at}stanford.edu.
Author contributions: O.A. and G.H.G. designed research; O.A. performed research; O.A. analyzed data; and O.A. and G.H.G. wrote the paper.
Conflict of interest statement: No conflicts declared.
Abbreviations: EVD, eigenvalue decomposition; HOEVD, higher-order EVD; SVD, singular-value decomposition.
↵ ¶ In this article, m̂ denotes a matrix, |v 〉 denotes a column vector, and 〈u| denotes a row vector, such that m̂|v 〉, 〈u|m̂, and 〈u|v 〉 all denote inner products, and |v 〉〈u| denotes an outer product.