Journal of Bioinformatics and Computational Biology

Motivation: For DNA microarrays, the gain in certainty by performing multiple experimental repeats is offset by the high cost of each experiment. In a typical experiment, two independent measurements (that is, data from two separate arrays) are combined to yield a single comparative index per gene. Thus, although one uses 2n arrays and performs 2n independent measurements, one obtains only n comparative measurements. We addressed the question: how many of the potential n² comparisons derivable from such data are actually independent, and what effect do these additional comparisons have on the false positive rate. Results: We show there are precisely 2n - 1 independent comparisons available from among the n² possibilities. Applying these additional n - 1 independent comparisons to experimental and simulated data reduced the false positive rate by as much as 10-fold, with excellent agreement between experimental and theoretical false positive rates.

Motivation: It is commonly believed that suitable analysis of microarray gene expression profile data can lead to better understanding of diseases, and better ways to diagnose and treat diseases. To achieve those goals, it is of interest to discover the gene interaction networks, and perhaps even pathways, underlying given diseases from such data. In this paper, we consider methods for efficiently discovering highly differentiative gene groups (HDGG), which may provide insights on gene interaction networks. HDGGs are groups of genes which completely or nearly completely characterize the diseased or normal tissues. Discovering HDGGs is challenging, due to the high dimensionality of the data.

Results: Our methods are based on the novel concept of gene clubs. A gene club consists of a set of genes having high potential to be interactive with each other. The methods can (i) efficiently discover signature HDGGs which completely characterize the diseased and the normal tissues respectively, (ii) find strongest or near strongest HDGGs containing any given gene, and (iii) find much stronger HDGGs than previous methods. As part of the experimental evaluation, the methods are applied to colon, prostate, ovarian, and breast cancer, and leukemia and so on. Some of the genes in the extracted signature HDGGs have known biological functions, and some have attracted little attention in biology and medicine. We hope that appropriate study on them can lead to medical breakthroughs. Some HDGGs for colon and prostate cancers are listed here. The website listed below contains HDGGs for the other cancers.

Availability: HDGG is implemented in C++ and runs on Unix or Windows platform. The code is available at: .

In comprehensive functional genomics projects, systematic analysis of phenotypes is vital. However, conventional phenotypic screening is done mainly by imprecise visual observation of qualitative traits, and, therefore, in silico screening techniques for quantitative traits are required. In this report, we propose in silico phenotypic screening method that utilizes a Gaussian mixture model for the trait distribution in the offspring of a mutagenized line and the likelihood ratio test between the estimated Gaussian mixture model and the wild-type single Gaussian model. In order to evaluate the proposed method, we performed a screening experiment using real trait data of Arabidopsis. In this experiment, the proposed screening method properly distinguished the mutant line from the wild-type line. Furthermore, we conducted power analysis of the proposed method and two conventional methods under various simulated conditions of sample size and distribution of trait frequency. The result of the power analysis confirmed the effectiveness of the proposed method compared to the conventional methods.

Since microarray gene expression data do not contain sufficient information for estimating accurate gene networks, other biological information has been considered to improve the estimated networks. Recent studies have revealed that highly conserved proteins that exhibit similar expression patterns in different organisms, have almost the same function in each organism. Such conserved proteins are also known to play similar roles in terms of the regulation of genes. Therefore, this evolutionary information can be used to refine regulatory relationships among genes, which are estimated from gene expression data. We propose a statistical method for estimating gene networks from gene expression data by utilizing evolutionarily conserved relationships between genes. Our method simultaneously estimates two gene networks of two distinct organisms, with a Bayesian network model utilizing the evolutionary information so that gene expression data of one organism helps to estimate the gene network of the other. We show the effectiveness of the method through the analysis on Saccharomyces cerevisiae and Homo sapiens cell cycle gene expression data. Our method was successful in estimating gene networks that capture many known relationships as well as several unknown relationships which are likely to be novel. Supplementary information is available at .

The protein structures determined by NMR (Nuclear Magnetic Resonance Spectroscopy) are not as detailed and accurate as those by X-ray crystallography and are often underdetermined due to the inadequate distance data available from NMR experiments. The uses of NMR-determined structures in such important applications as homology modeling and rational drug design have thus been severely limited. Here we show that with the increasing numbers of high quality protein structures being determined, a computational approach to enhancing the accuracy of the NMR-determined structures becomes possible by deriving additional distance constraints from the distributions of the distances in databases of known protein structures. We show through a survey on 462 NMR structures that, in fact, many inter-atomic distances in these structures deviate considerably from their database distributions and based on the refinement results on 10 selected NMR structures that these structures can actually be improved significantly when a selected set of distances are constrained within their high probability ranges in their database distributions.

The constrained bipartite matching (CBM) problem is a variant of the classical bipartite matching problem that has been well studied in the Combinatorial Optimization community. The input to CBM is an edge-weighted complete bipartite graph in which there are a same number of vertices on both sides and vertices on one side are sequentially ordered while vertices on the other side are partitioned and connected into disjoint directed paths. In a feasible matching, a path must be mapped to consecutive vertices on the other side. The optimization goal is to find a maximum or a minimum weight perfect matching. Such an optimization problem has its applications to scheduling and protein Nuclear Magnetic Resonance peak assignment. It has been shown to be NP-hard and MAX SNP-hard if the perfectness requirement is dropped. In this paper, more results on the inapproximability are presented and IDA*, a memory efficient variant of the well known A* search algorithm, is utilized to solve the problem. Accordingly, search heuristics and a set of heuristic evaluation functions are developed to assist the search, whose effectiveness is demonstrated by a simulation study using real protein NMR backbone resonance assignment instances.

Understanding how protein folds into a functional native structure is arguably one of the most challenging problems remaining in computational biology. Currently, the protein folding mechanism is often characterized by calculating the free energy landscape in terms of various reaction coordinates such as the fraction of native contacts, the radius of gyration, the RMS deviation from the native and so on. In this paper, we present a wavelet approach towards understanding the global state changes during protein folding. The approach is based on the wavelet analysis on the trajectories of various reaction coordinates to identify the significant intermediate states or structural motifs in the folding process. We demonstrate through an example protein Trp-cage that this approach extracts crucial information about protein folding intermediate states as well as the time correlation among these states. Furthermore, the current approach reveals a meaningful structural pattern that had been overlooked in previous works, which provides a better understanding of the folding mechanism as well as the limitation of the current force fields.

Prediction of biological functions of genes is an important issue in basic biology research and has applications in drug discoveries and gene therapies. Previous studies have shown either gene expression data or protein-protein interaction data alone can be used for predicting gene functions. In particular, clustering gene expression profiles has been widely used for gene function prediction. In this paper, we first propose a new method for gene function prediction using protein-protein interaction data, which will facilitate combining prediction results based on clustering gene expression profiles. We then propose a new method to combine the prediction results based on either source of data by weighting on the evidence provided by each. Using protein-protein interaction data downloaded from the GRID database, published gene expression profiles from 300 microarray experiments for the yeast S. cerevisiae, we show that this new combined analysis provides improved predictive performance over that of using either data source alone in a cross-validated analysis of the MIPS gene annotations. Finally, we propose a logistic regression method that is flexible enough to combine information from any number of data sources while maintaining computational feasibility.

Local structural information is supposed to be frequently encoded in local amino acid sequences. Previous research only indicated that some local structure positions have specific residue preferences in some particular local structures. However, correlated pairwise replacements for interacting residues in recurrent local structural motifs from unrelated proteins have not been studied systematically. We introduced a new method fusing statistical covariation analysis and local structure-based alignment. Systematic analysis of structure-based multiple alignments of recurrent local structures from unrelated proteins in representative subset of Protein Databank indicates that covarying residue pairs with statistical significance exist in local structural motifs, in particular β-turns and helix caps. These residue pairs are mostly linked through polar functional groups with direct or indirect hydrogen bonding. Hydrophobic interaction is also a major factor in constraining pairwise amino acid residue replacement in recurrent local structures. We also found correlated residue pairs that are not clearly linked with through-space interactions. The physical constrains underlying these covariations are less clear. Overall, covarying residue pairs with statistical significance exist in local structures from unrelated proteins. The existence of sequence covariations in local structural motifs from unrelated proteins indicates that many relics of local relations are still retained in the tertiary structures after protein folding. It supports the notion that some local structural information is encoded in local sequences and the local structural codes could play important roles in determining native state protein folding topology.

The reliability of the algorithms for ratio estimation in two-color microarray image analysis is very important, as these ratios build up the primary source of information for the subsequent analytical procedures (normalization, clustering, classification, etc). Although various algorithms already exist, there is still a need to develop procedures having higher levels of accuracy and robustness. We present a statistical procedure for the detection and removal of aberrant pixels in two-color microarray images. It is based on a linear regression approach, assuming reasonably high level of correlation between the two color channels. This procedure ensures more robust ratio estimation for the spots in both linear regression and traditional segmentation algorithms. The developed algorithms have been evaluated using simulated artificial images and experimental images of different designs. A demonstration version of the software can be downloaded from .

We present a dimensionless fit index for phylogenetic trees that have been constructed from distance matrices. It is designed to measure the quality of the fit of the data to a tree in absolute terms, independent of linear transformations on the distance matrix. The index can be used as an absolute measure to evaluate how well a set of data fits to a tree, or as a relative measure to compare different methods that are expected to produce the same tree. The usefulness of the index is demonstrated in three examples.

Hidden Markov Models (HMM) can be extremely useful tools for the analysis of data from biological sequences, and provide a probabilistic model of protein families. Most reviews and general introductions follow the excellent tutorial by Rabiner,¹ where the focus is outside biology. Mendel's famous experiments in plant hybridisation were published in 1866 and are often considered the icebreaking work of modern genetics. He had no prior knowledge of the dual nature of genes, but through a series of experiments he was able to anticipate the hidden concept and name it "Elemente". In this paper we present the background, theory and algorithms of HMM based on examples from Mendel's experiments, and introduce the toolbox "mendelHMM". This approach is considered to have some intuitive advantages in a biological and bioinformatical setting. Applications to analysing bio-sequences like nucleic acids and proteins are also discussed.