Journal of Bioinformatics and Computational Biology

It is well-known that functionally related genes occur in a physically clustered form, especially operons in bacteria. By leveraging on this fact, there has recently been an interesting problem formulation known as gene team model, which searches for a set of genes that co-occur in a pair of closely related genomes. However, many gene teams, even experimentally verified operons, frequently scatter within other genomes. Thus, the gene team model should be refined to reflect this observation.

In this paper, we generalized the gene team model, that looks for gene clusters in a physically clustered form, to multiple genome cases with relaxed constraints. We propose a novel hybrid pattern model that combines the set and the sequential pattern models. Our model searches for gene clusters with and/or without physical proximity constraint. This model is implemented and tested with 97 genomes (120 replicons). The result was analyzed to show the usefulness of our model. We also compared the result from our hybrid model to those from the traditional gene team model. We also show that predicted gene teams can be used for various genome analysis: operon prediction, phylogenetic analysis of organisms, contextual sequence analysis and genome annotation. Our program is fast enough to provide a service on the web at . Users can select any combination of 97 genomes to predict gene teams.

LTR retrotransposons constitute one of the most abundant classes of repetitive elements in eukaryotic genomes. In this paper, we present a new algorithm for detection of full-length LTR retrotransposons in genomic sequences. The algorithm identifies regions in a genomic sequence that show structural characteristics of LTR retrotransposons. Three key components distinguish our algorithm from that of current software — (i) a novel method that preprocesses the entire genomic sequence in linear time and produces high quality pairs of LTR candidates in run-time that is constant per pair, (ii) a thorough alignment-based evaluation of candidate pairs to ensure high quality prediction, and (iii) a robust parameter set encompassing both structural constraints and quality controls providing users with a high degree of flexibility. We implemented our algorithm into a software program called LTR_par, which can be run on both serial and parallel computers. Validation of our software against the yeast genome indicates superior results in both quality and performance when compared to existing software. Additional validations are presented on rice BACs and chimpanzee genome.

In this paper, we develop a machine learning system for determining gene functions from heterogeneous data sources using a Weighted Naive Bayesian network (WNB). The knowledge of gene functions is crucial for understanding many fundamental biological mechanisms such as regulatory pathways, cell cycles and diseases. Our major goal is to accurately infer functions of putative genes or Open Reading Frames (ORFs) from existing databases using computational methods. However, this task is intrinsically difficult since the underlying biological processes represent complex interactions of multiple entities. Therefore, many functional links would be missing when only one or two sources of data are used in the prediction. Our hypothesis is that integrating evidence from multiple and complementary sources could significantly improve the prediction accuracy. In this paper, our experimental results not only suggest that the above hypothesis is valid, but also provide guidelines for using the WNB system for data collection, training and predictions. The combined training data sets contain information from gene annotations, gene expressions, clustering outputs, keyword annotations, and sequence homology from public databases. The current system is trained and tested on the genes of budding yeast Saccharomyces cerevisiae. Our WNB model can also be used to analyze the contribution of each source of information toward the prediction performance through the weight training process. The contribution analysis could potentially lead to significant scientific discovery by facilitating the interpretation and understanding of the complex relationships between biological entities.

A major challenge for genomewide disease association studies is the high cost of genotyping large number of single nucleotide polymorphisms (SNPs). The correlations between SNPs, however, make it possible to select a parsimonious set of informative SNPs, known as "tagging" SNPs, able to capture most variation in a population. Considerable research interest has recently focused on the development of methods for finding such SNPs. In this paper, we present an efficient method for finding tagging SNPs. The method does not involve computation-intensive search for SNP subsets but discards redundant SNPs using a feature selection algorithm. In contrast to most existing methods, the method presented here does not limit itself to using only correlations between SNPs in local groups. By using correlations that occur across different chromosomal regions, the method can reduce the number of globally redundant SNPs. Experimental results show that the number of tagging SNPs selected by our method is smaller than by using block-based methods.

Supplementary website: .

High throughput expression profiling and genotyping technologies provide the means to study the genetic determinants of population variation in gene expression variation. In this paper we present a general statistical framework for the simultaneous analysis of gene expression data and SNP genotype data measured for the same cohort. The framework consists of methods to associate transcripts with SNPs affecting their expression, algorithms to detect subsets of transcripts that share significantly many associations with a subset of SNPs, and methods to visualize the identified relations. We apply our framework to SNP-expression data collected from 50 breast cancer patients. Our results demonstrate an overabundance of transcript-SNP associations in this data, and pinpoint SNPs that are potential master regulators of transcription. We also identify several statistically significant transcript-subsets with common putative regulators that fall into well-defined functional categories.

Machine learning techniques offer a viable approach to cluster discovery from microarray data, which involves identifying and classifying biologically relevant groups in genes and conditions. It has been recognized that genes (whether or not they belong to the same gene group) may be co-expressed via a variety of pathways. Therefore, they can be adequately described by a diversity of coherence models. In fact, it is known that a gene may participate in multiple pathways that may or may not be co-active under all conditions. It is therefore biologically meaningful to simultaneously divide genes into functional groups and conditions into co-active categories — leading to the so-called biclustering analysis. For this, we have proposed a comprehensive set of coherence models to cope with various plausible regulation processes. Furthermore, a multivariate biclustering analysis based on fusion of different coherence models appears to be promising because the expression level of genes from the same group may follow more than one coherence models. The simulation studies further confirm that the proposed framework enjoys the advantage of high prediction performance.

The polymerase chain reaction (PCR) is a fundamental tool of molecular biology. Quantitative PCR is the gold-standard methodology for determination of DNA copy numbers, quantitating transcription, and numerous other applications. A major barrier to large-scale application of PCR for quantitative genomic analyses is the current requirement for manual validation of individual PCRs to ensure generation of a single product. This typically requires visual inspection either of gel electrophoreses or temperature dissociation ("melting") curves of individual PCRs — a time-consuming and costly process.

Here we describe a robust computational solution to this fundamental problem. Using a training set of 10 080 reactions comprising multiple quantitative PCRs from each of 1728 unique human genomic amplicons, we developed a support vector machine classifier capable of discriminating single-product PCRs with better than 99% accuracy. This approach has broad utility, and eliminates a major bottleneck to widespread application of PCR for high-throughput genomic applications.

As the first step toward a multi-scale, hierarchical computational approach for membrane protein structure prediction, the packing of transmembrane helices was modeled at the residue and atom levels, respectively. For predictions at the residue level, the helix-helix and helix-membrane interactions were described by a set of knowledge-based energy functions. For predictions at the atom level, CHARMM19 force field was used. To facilitate the system to overcome energy barriers, the Wang–Landau method was employed, where a random walk is performed in the energy space with a uniform probability. Native-like structures were predicted at both levels for two model systems, each of which consists of two transmembrane helices. Interestingly, consistent results were obtained from simulations at the residue and atom levels for the same system, strongly suggesting the feasibility of a hierarchical approach for membrane protein structure predictions.

In our effort to elucidate the systems biology of the model organism, Escherichia coli, we have developed a mathematical model that simulates the allosteric regulation for threonine biosynthesis pathway starting from aspartate. To achieve this goal, we used kMech, a Cellerator language extension that describes enzyme mechanisms for the mathematical modeling of metabolic pathways. These mechanisms are converted by Cellerator into ordinary differential equations (ODEs) solvable by Mathematica™. In this paper, we describe a more flexible model in Cellerator, which generalizes the Monod, Wyman, Changeux (MWC) model for enzyme allosteric regulation to allow for multiple substrate, activator and inhibitor binding sites. Furthermore, we have developed a model that describes the behavior of the bifunctional allosteric enzyme aspartate kinase I-homoserine dehydrogenase I (AKI-HDHI). This model predicts the partition of enzyme activities in the steady state which paves the way for a more generalized prediction of the behavior of bifunctional enzymes.

The conserved hydrophobic core is an important feature of a family of protein domains. We suggest a procedure for finding and the analysis of conserved hydrophobic cores. The procedure is based on using an original program called CluD (). Conserved hydrophobic cores of several families including homeodomains and interlock-containing domains are described. Hydrophobic clusters on some protein-DNA and protein-protein interfaces were also analyzed.

Identification of potentially amyloidogenic regions in polypeptide chains is very important because the amyloid fibril formation can be induced in most normal proteins. In our work we suggest a new method to detect amyloidogenic regions in protein sequence. It is based on the assumption that packing is tight inside an amyloid and therefore regions which could potentially pack well would have a tendency to form amyloids. This means that the regions with strong expected packing of residues would be responsible for the amyloid formation. We use this property to identify potentially amyloidogenic regions in proteins basing on their amino acid sequences only. Our predictions are consistent with known disease-related amyloidogenic regions for 8 of 11 amyloid-forming proteins and peptides in which the positions of amyloidogenic regions have been revealed experimentally. Predictions of the regions which are responsible for the formation of amyloid fibrils in proteins unrelated to disease have been also done.

Sub-unit vaccines are synthetic or recombinant peptides representing T- or B-cell epitopes of major protein antigens from a particular pathogen. Epitope selection requires the synthesis of peptides that overlap the protein sequences and screening for the most effective ones. In this study a new method of immunogenic peptide selection based on the analysis of information structure of protein sequences is suggested. The analysis of known B-cell epitope location in the information structure of Aspergillus fumigatus proteins Asp f 2 and Asp f 3 has shown that epitopes are scattered along the sequences of proteins for the exception of sites with Increased Degree Information Coordination (IDIC). Based on these results peptides from different allergens such as Asp f 2, Der p 1, and Fel d 1 were selected and produced in a recombinant form in the context of yeast virus-like particles (VLPs). Immunization of mice with VLPs containing peptides form allergens has induced the production of IgG able to recognize full-length antigens. This result suggests that the analysis of information structure of proteins can be used for the selection of peptides possessing cryptic B-cell epitope activity.

The eukaryotic pathogen Leishmania donovani possesses a housekeeping protein Elongation-Factor-1α (EF-1α) which has been found to be unexpectedly involved in the pathogen's virulence. Because it is associated with virulence and essential for cell survival, this protein is an attractive choice for drug targeting; however, its sequence is highly similar (> 80% sequence identity) to that of its human homolog, rendering it a risky choice for a drug target.

The chief difference between these two proteins has been found to be a 12 amino acid sequence present in human EF-1α but absent from leishmania EF-1α. Furthermore, it has been shown that this 12 amino acid insert in the human sequence corresponds to a hairpin loop on the surface of the protein. In this study, we searched for those spatial features in leishmania EF-1α that are impacted or obscured by the extra hairpin loop in the human counterpart.

We have also conducted a large-scale in silico screening for small molecules that could plausibly bind to these protein features. While experimental evidence is required to verify our results, our findings thus far appear to support this approach as a new strategy for the development of antagonists against pathogenic targets having close human homologs.

The third complementary determining region of the immunoglobulin heavy chain (CDR H3) is one of the more difficult structures to model due to genetic reasons. However, the conformation of proximal to β-framework ("torso") part of the CDR H3 is very predictable. Current "CDR's canonical classes" theory is based on identifying the key positions, H94 and H101. We can determine the CDR H3 "torso" structure if arginine or lysine is present in the H94 position and/or aspartic acid in the H101 position. We target the case characterized by the absence of key residues in both the H94 and H101 positions. There has not been discussion on this case in the literature. 51 CDR H3 structures of this nature are analyzed and we established new sequence-structure rules. These rules contribute to more accurate modeling of the antibody's structure.

One of the main goals of analysing DNA sequences is to understand the temporal and positional information that specifies gene expression. An important step in this process is the recognition of gene expression regulatory elements. Experimental procedures for this are slow and costly. In this paper we present a computational non-supervised algorithm that facilitates the process by statistically identifying the most likely regions within a putative regulatory sequence. A probabilistic technique is presented, based on the approximation of regulatory DNA with a Markov chain, for the location of putative transcription factor binding sites in a single stretch of DNA. Hereto we developed a procedure to approximate the order of Markov model for a given DNA sequence that circumvents some of the prohibitive assumptions underlying Markov modeling. Application of the algorithm to data from 55 genes in five species shows the high sensitivity of this Markov search algorithm. Our algorithm does not require any prior knowledge in the form of description or cross-genomic comparison; it is context sensitive and takes DNA heterogeneity into account.

A pattern recognition software PlatProm, which takes into consideration both sequence-specific and structure-specific features in the genetic environment of the promoter sites and identifies transcription start points with a very high accuracy was used to reveal potentially transcribed regions in the genomes of two bacterial species. Along with the expected promoters located upstream from coding sequences PlatProm identified several hundred of very similar signals in other intergenic regions and within coding sequences. Homologous genes of Escherichia coli and Salmonella typhimurium, containing potential promoters on the template strand are suggested as putative targets for regulations by antisense RNA-products (aRNAs).

A comparative analysis of electrostatic patterns for 359 σ⁷⁰-specific promoters and 359 nonpromoter regions on electrostatic map of Escherichia coli genome was carried out. It was found that DNA is not a uniformly charged molecule. There are some local inhomogeneities in its electrostatic profile which correlate with promoter sequences. Electrostatic patterns of promoter DNAs can be specified due to the presence of some distinctive motifs which differ for different promoter groups and may be involved as signal elements in differential recognition of various promoters by the enzyme. Some specific electrostatic elements which are responsible for modulating promoter activities due to ADP-ribosylation of RNA polymerase α-subunit were found in far upstream regions of T4 phage early promoters and E. coli ribosomal promoters.

The identification of cis-elements (motifs) in the regulatory regions of higher eukaryotes is an important and challenging problem in computational biology. Eukaryotic transcriptional regulatory mechanisms pose several difficulties for promoter analysis: including a high variance in the motif locations, frequently large divergence from motif consensus patterns, and a large amount of repetitive elements (confusing to many motif finding procedures). One promising approach to this difficult problem involves cross-species comparison. In this work we analyzed the full-length regulatory regions of genes involved in the G-protein coupling MAP kinase pathway and compared the results with ribosomal genes using human, mouse and rat genomic data. We found 19 high likely transcription factors (TFs) candidates for MAPK and 12 TFs for the ribosomal dataset. In the case of the MAPK dataset, regulatory regions of genes functionally grouped as receptors and MAP-core genes were found mostly highly conserved across the three species.

We demonstrate how automated text analysis can be used to support the large-scale analysis of metabolic and regulatory pathways by deriving pathway maps from textual descriptions found in the scientific literature. The main assumption is that correct syntactic analysis combined with domain-specific heuristics provides a good basis for relation extraction. Our method uses an algorithm that searches through the syntactic trees produced by a parser based on a Referent Grammar formalism, identifies relations mentioned in the sentence, and classifies them with respect to their semantic class and epistemic status (facts, counterfactuals, hypotheses). The semantic categories used in the classification are based on the relation set used in KEGG (Kyoto Encyclopedia of Genes and Genomes), so that pathway maps using KEGG notation can be automatically generated. We present the current version of the relation extraction algorithm and an evaluation based on a corpus of abstracts obtained from PubMed. The results indicate that the method is able to combine a reasonable coverage with high accuracy. We found that 61% of all sentences were parsed, and 97% of the parse trees were judged to be correct. The extraction algorithm was tested on a sample of 300 parse trees and was found to produce correct extractions in 90.5% of the cases.

Quantitative time-series observation of gene expression is becoming possible, for example by cell array technology. However, there are no practical methods with which to infer network structures using only observed time-series data. As most computational models of biological networks for continuous time-series data have a high degree of freedom, it is almost impossible to infer the correct structures. On the other hand, it has been reported that some kinds of biological networks, such as gene networks and metabolic pathways, may have scale-free properties. We hypothesize that the architecture of inferred biological network models can be restricted to scale-free networks. We developed an inference algorithm for biological networks using only time-series data by introducing such a restriction. We adopt the S-system as the network model, and a distributed genetic algorithm to optimize models to fit its simulated results to observed time series data.

We have tested our algorithm on a case study (simulated data). We compared optimization under no restriction, which allows for a fully connected network, and under the restriction that the total number of links must equal that expected from a scale free network. The restriction reduced both false positive and false negative estimation of the links and also the differences between model simulation and the given time-series data.

We created an algorithm that allows high-throughput mapping of sense-antisense (SA) pairs of transcripts. By this method we mapped approximately 32 000 SA pairs of human mRNAs. Collected SA pairs were divided into three groups: SA pairs based on two or more UniGene clusters (17% of all sense-antisense pairs), SA pairs based on ESTs that belong to the same UniGene cluster (42%), and SA pairs formed by UniGene cluster and non-unique unclustered transcripts (41%). To study expression patterns of natural SA pairs we created a software application "Antisense Cluster Filter". We retrieved tissue expression data for all the transcripts forming identified SA pairs, including clustered and unclustered ones. After that, we selected 108 SA pairs represented by transcripts differentially regulated in human tumors. For each of these SA pairs one of the transcripts was expressed only in tumors, another one was expressed both in non-malignant and malignant tissues. Indicated SA pairs may represent a new class of tumor markers. An example of the tumor-specific natural antisense to C3orf4 mRNA is detailed.

Identifying regions of DNA with extreme statistical characteristics is an important aspect of the structural analysis of complete genomes. Linguistic methods, mainly based on estimating word frequency, can be used for this as they allow for the delineation of regions of low complexity. Low complexity may be due to biased nucleotide composition, by tandem- or dispersed repeats, by palindrome-hairpin structures, as well as by a combination of all these features. We developed software tools in which various numerical measures of text complexity are implemented, including combinatorial and linguistic ones. We also added Hurst exponent estimate to the software to measure dependencies in DNA sequences. By applying these tools to various functional genomic regions, we demonstrate that the complexity of introns and regulatory regions is lower than that of coding regions, whilst Hurst exponent is larger. Further analysis of promoter sequences revealed that the lower complexity of these regions is associated with long-range correlations caused by transcription factor binding sites.

We study and compare two classes of statistical criteria to assess the significance of exceptional words. Indeed, the Z-score-like criteria, or the normal approximation that is a strict equivalent, suffer from several drawbacks in terms of sensitivity and specificity. Thanks to the combinatorial structure of words, a computation of the exact P-value has been made possible by recent mathematical results. We study here the drawbacks of the Z-score, the choice of the threshold and the tightness to the P-value.

A major conclusion is that the normal approximation is always very poor and overestimates statistical significance.

We propose a general approach to compute the seed sensitivity, that can be applied to different definitions of seeds. It treats separately three components of the seed sensitivity problem — a set of target alignments, an associated probability distribution, and a seed model — that are specified by distinct finite automata. The approach is then applied to a new concept of subset seeds for which we propose an efficient automaton construction. Experimental results confirm that sensitive subset seeds can be efficiently designed using our approach, and can then be used in similarity search producing better results than ordinary spaced seeds.

A large portion of the usual eukaryotic genome is comprised of repetitive sequences. A common situation, when several related but different repeat families share the same conserved motif, complicates repeat classification and repeat boundary definition. If the repeats are aligned by the motif position, then the sequence profile (pattern) resulting from the alignment will represent overlapping of the profiles (patterns) corresponding to the individual families. A novel algorithm for the decomposition of overlapping patterns is proposed. It can be used with both continuous and gapped patterns. The technique is based on accumulation of simultaneously occurring pattern features found by cross-correlation procedure with limited lag length; thus, the name is Cumulative Local Cross-Correlation (referred further as CLCC). Its sensitivity is tested on human genomic sequences. Software implementation of the algorithm is available on request from the author.

The RNAKinetics server () is a web interface for the newly developed RNAKinetics software. The software models the dynamics of RNA secondary structure by the means of kinetic analysis of folding transitions of a growing RNA molecule. The result of the modeling is a kinetic ensemble, i.e. a collection of RNA structures that are endowed with probabilities, which depend on time. This approach gives comprehensive probabilistic description of RNA folding pathways, revealing important kinetic details that are not captured by the traditional structure prediction methods. The access to the RNAKinetics server is free.

Archaea, bacteria and eukaryotes represent the main kingdoms of life. Is there any trend for amino acid compositions of proteins found in full genomes of species of different kingdoms? What is the percentage of totally unstructured proteins in various proteomes? We obtained amino acid frequencies for different taxa using 195 known proteomes and all annotated sequences from the Swiss–Prot data base. Investigation of the two data bases (proteomes and Swiss–Prot) shows that the amino acid compositions of proteins differ substantially for different kingdoms of life, and this difference is larger between different proteomes than between different kingdoms of life. Our data demonstrate that there is a surprisingly small selection for the amino acid composition of proteins for higher organisms (eukaryotes) and their viruses in comparison with the "random" frequency following from a uniform usage of codons of the universal genetic code. On the contrary, lower organisms (bacteria and especially archaea) demonstrate an enhanced selection of amino acids. Moreover, according to our estimates, 12%, 3% and 2% of the proteins in eukaryotic, bacterial and archaean proteomes are totally disordered, and long (> 41 residues) disordered segments are found to occur in 16% of arhaean, 20% of eubacterial and 43% of eukaryotic proteins for 19 archaean, 159 bacterial and 17 eukaryotic proteomes, respectively. A correlation between amino acid compositions of proteins of various taxa, show that the highest correlation is observed between eukaryotes and their viruses (the correlation coefficient is 0.98), and bacteria and their viruses (the correlation coefficient is 0.96), while correlation between eukaryotes and archaea is 0.85 only.

We present a new classification scheme of the genetic code. In contrast to the standard form it clearly shows five codon symmetries: codon-anticodon, codon-reverse codon, and sense-antisense symmetry, as well as symmetries with respect to purine-pyrimidine (A versus G, U versus C) and keto-aminobase (G versus U, A versus C) exchanges. We study the number of tRNA genes of 16 archaea, 81 bacteria and 7 eucaryotes to analyze whether these symmetries are reflected in the corresponding tRNA usage patterns. Two features are especially striking: reverse stop codons do not have their own tRNAs (just one exception in human), and A** anticodons are significantly suppressed. Our classification scheme of the genetic code and the identified tRNA usage patterns support recent speculations about the early evolution of the genetic code. In particular, pre-tRNAs might have had the ability to bind their codons in two directions to the corresponding codons.