In this report, we designed a procedure for exploring the cellular relationships from the sets of characteristic genes in distinctive cell types, by using partial canonical correlation analysis. We applied the present procedure to the characteristic gene sets of seven subtypes of testicular germ cell tumors in a previous report. The cellular relationships were well reconstructed, consistent with the general histologic lineage model, and new implications for the subtype differentiation were found. In particular, the correspondence between the inferred relationships and the functional characterizations of constituent genes suggests a hypothesis for the classification between seminoma and embryonal carcinoma. The partial canonical correlation analysis is also appropriate for revealing new features of cellular relationships, based on the transcriptional programs. Thus, the present procedure helps to create a macroscopic view of the cellular relationships, by following the detection of the characteristically expressed genes.

We developed a procedure for indentifying transcriptional master regulators (MRs) related to special biological phenomena, such as diseases, in conjunction with network screening and inference. Network screening is a system for detecting activated transcriptional regulatory networks under particular conditions, based on the estimation of the graph structure consistency with the measured data. Since the network screening utilizes the known transcriptional factor (TF)-gene relationships as the experimental evidence for the molecular relationships, its performance depends on the ensemble of known TF networks used for its analysis. To compensate for its restrictions, a network inference method, the path consistency algorithm, is concomitantly utilized to identify MRs. The performance is illustrated by means of the known MRs in brain tumors that were computationally inferred and experimentally verified. As a result, the present procedure worked well for identifying MRs, in comparison to the previous computational selection for experimental verification.

The assessment of co-expressed genes is an initial step to investigate the gene regulatory system in a microarray analysis. We designed a simple method to assess co-expressed genes from the expression profiles, based on the path consistency (PC) algorithm, which systematically infers a causal graph. The PC algorithm is simply modified for the frequent occurrence of high correlations between expression profiles, which causes an accidental stop of the algorithm by the violation of a numerical calculation. By utilizing the flexible features of the algorithm, biological information about co-expressed genes can be introduced into the algorithm. The performance is illustrated by the application to the gene profiles of operons: 1168 gene profiles in 137 known operons in Escherichia coli. By the improved algorithm, more than 80% of the operons were correctly detected, and less than one gene per operon was falsely detected. The performance promises the wide feasibility of the present method for the assessment of co-expressed genes from microarray data on a genomic scale.

MOTIVATION: The computational prediction of protein-protein interactions is currently a major issue in bioinformatics. Recently, a variety of co-evolution-based methods have been investigated toward this goal. In this study, we introduced a partial correlation coefficient as a new measure for the degree of co-evolution between proteins, and proposed its use to predict protein-protein interactions. RESULTS: The accuracy of the prediction by the proposed method was compared with those of the original mirror tree method and the projection method previously developed by our group. We found that the partial correlation coefficient effectively reduces the number of false positives, as compared with other methods, although the number of false negatives increased in the prediction by the partial correlation coefficient. AVAILABILITY: The R script for the prediction of protein-protein interactions reported in this manuscript is available at http://timpani.genome.ad.jp/~parco/

We consider the protein threading problem with profiles in which constraints on distances between residues are given. Though it is known that protein threading with profiles can be solved efficiently using dynamic programming, we prove that protein threading with profiles and constraints is NP-hard. Moreover, we show a strong hardness result on the approximation of an optimal threading satisfying all the constraints. On the other hand, we develop two practical algorithms: CLIQUETHREAD and BBDPTHREAD. CLIQUETHREAD reduces the threading problem to the maximum edge-weight clique problem, whereas BBDPTHREAD combines dynamic programming and branch-and-bound techniques. We perform computational experiments using protein structure data in PDB (protein data bank). The results show that constraints are useful to improve the alignment accuracy. These also show that BBDPTHREAD is in general faster than CLIQUETHREAD for larger size proteins whereas CLIQUETHREAD is useful if there does not exist a feasible threading.

UNLABELLED: We constructed a website for inferring a network by applying the graphical Gaussian model, from a large amount of data, including redundant information. The available tools on the website are based on a system, named ASIAN (Automatic System for Inferring A Network), in combination with the two methods in our previous papers, which were designed to analyze gene expression profiles on a genomic scale. One of the remarkable features of the website is its ability to infer a network, concomitant with hierarchical clustering and the following estimation of cluster boundaries. AVAILABILITY: http://eureka.ims.u-tokyo.ac.jp/asian

MOTIVATION: Recent advances in DNA microarray technologies have made it possible to measure the expression levels of thousands of genes simultaneously under different conditions. The data obtained by microarray analyses are called expression profile data. One type of important information underlying the expression profile data is the 'genetic network,' that is, the regulatory network among genes. Graphical Gaussian Modeling (GGM) is a widely utilized method to infer or test relationships among a plural of variables. RESULTS: In this study, we developed a method combining the cluster analysis with GGM for the inference of the genetic network from the expression profile data. The expression profile data of 2467 Saccharomyces cerevisiae genes measured under 79 different conditions (Eisen et al., PROC: Natl Acad. Sci. USA, 95, 14683-14868, 1998) were used for this study. At first, the 2467 genes were classified into 34 clusters by a cluster analysis, as a preprocessing for GGM. Then, the expression levels of the genes in each cluster were averaged for each condition. The averaged expression profile data of 34 clusters were subjected to GGM, and a partial correlation coefficient matrix was obtained as a model of the genetic network of S. cerevisiae. The accuracy of the inferred network was examined by the agreement of our results with the cumulative results of experimental studies.

MOTIVATION: Following an extensive search for orthologous genes between the complete genomes from archaea and bacteria, the spatial association of the orthologs has been investigated in terms of synteny, the conservation of the order of neighboring genes. However, the relationships between the relative locations of remote orthologs over entire genomes have not been shown. RESULTS: Comprehensive comparisons between the locations of orthologs on nineteen archaeal and bacterial genomes are presented by the location to location correspondence based on the gene-location distance. When the two genomes are rotated such that a pair of orthologs with the shortest distance is set in the same angle, a statistically significant number of orthologs maintain their relative locations between the genomes. Even by the short distances at the 5% significance level, the rotations are restricted within a narrow range, suggesting an intrinsic angle for realizing similar locations between the orthologs in each genome pair. Furthermore, the rotations in the restricted range agree with the replication origin and terminus sites for the analyzed genomes where such sites are known. The relationship between location-maintained orthologs and gene function is also discussed.

MOTIVATION: Gene expression profile data are rapidly accumulating due to advances in microarray techniques. The abundant data are analyzed by clustering procedures to extract the useful information about the genes inherent in the data. In the clustering analyses, the systematic determination of the boundaries of gene clusters, instead of by visual inspection and biological knowledge, still remains challenging. RESULTS: We propose a statistical procedure to estimate the number of clusters in the hierarchical clustering of the expression profiles. Following the hierarchical clustering, the statistical property of the profiles at the node in the dendrogram is evaluated by a statistics-based value: the variance inflation factor in the multiple regression analysis. The evaluation leads to an automatic determination of the cluster boundaries without any additional analyses and any biological knowledge of the measured genes. The performance of the present procedure is demonstrated on the profiles of 2467 yeast genes, with very promising results. AVAILABILITY: A set of programs will be electronically sent upon request. CONTACT: [email protected]; [email protected]

MOTIVATION: Data on the entire structures of organelle and bacterial genomes, most of which are known to be circular, have accumulated at a rapid pace. This information enables us to utilize the locations of homologous gene pairs for measuring the dissimilarity between complete genomic structures. RESULTS: A macroscopic distance is presented for comparing circular genomes from their overall structures, on the basis of the locations of two pairs of homologous genes on the compared genomes. The novel aspect of our method is that the comparison between the genomes automatically reveals a relationship based on the information on all gene locations, by incorporating the mobility of each gene, which includes not only the gene order, but also the relative location between gene pairs. The plausibility of the newly defined distances is evaluated by means of 44 mitochondrial genomes. The genome distance shows high performance for quantitatively describing the differences between the gene organizations of the genomes. AVAILABILITY: Since the programs implementing these calculations require well-arranged gene organization data, they have not been released yet. However, one of the authors will analyze circular genomes upon request. Data on the gene organizations may be submitted electronically to the address below.