GENOME: a rapid coalescent-based whole genome simulator

Summary: GENOME proposes a rapid coalescent-based approach tosimulate whole genome data. In addition to features of standardcoalescent simulators, the program allows for recombinationrates to vary along the genome and for flexible population histories.Within small regions, we have evaluated samples simulated byGENOME to verify that GENOME provides the expected LD patternsand frequency spectra. The program can be used to study thesampling properties of any statistic for a whole genome study. Availability: The program and C++ source code are availableonline at http://www.sph.umich.edu/csg/liang/genome/ Contact: lianglim{at}umich.edu Supplementary information: Supplementary data are availableat Bioinformatics online. Associate Editor: Martin Bishop     

Align human interactome with phenome to identify causative genes and networks underlying disease families

Motivation: Understanding the complexity in gene–phenotyperelationship is vital for revealing the genetic basis of commondiseases. Recent studies on the basis of human interactome andphenome not only uncovers prevalent phenotypic overlap and geneticoverlap between diseases, but also reveals a modular organizationof the genetic landscape of human diseases, providing new opportunitiesto reduce the complexity in dissecting the gene–phenotypeassociation. Results: We provide systematic and quantitative evidence thatphenotypic overlap implies genetic overlap. With these results,we perform the first heterogeneous alignment of human interactomeand phenome via a network alignment technique and identify 39disease families with corresponding causative gene networks.Finally, we propose AlignPI, an alignment-based framework topredict disease genes, and identify plausible candidates for70 diseases. Our method scales well to the whole genome, asdemonstrated by prioritizing 6154 genes across 37 chromosomeregions for Crohn's disease (CD). Results are consistent witha recent meta-analysis of genome-wide association studies forCD. Availability: Bi-modules and disease gene predictions are freelyavailable at the URL http://bioinfo.au.tsinghua.edu.cn/alignpi/ Contact: ruijiang{at}tsinghua.edu.cn Supplementary information: Supplementary data are availableat Bioinformatics online. Associate Editor: Trey Ideker     

Fitting a geometric graph to a protein-protein interaction network

Motivation: Finding a good network null model for protein–proteininteraction (PPI) networks is a fundamental issue. Such a modelwould provide insights into the interplay between network structureand biological function as well as into evolution. Also, network(graph) models are used to guide biological experiments anddiscover new biological features. It has been proposed thatgeometric random graphs are a good model for PPI networks. Ina geometric random graph, nodes correspond to uniformly randomlydistributed points in a metric space and edges (links) existbetween pairs of nodes for which the corresponding points inthe metric space are close enough according to some distancenorm. Computational experiments have revealed close matchesbetween key topological properties of PPI networks and geometricrandom graph models. In this work, we push the comparison furtherby exploiting the fact that the geometric property can be testedfor directly. To this end, we develop an algorithm that takesPPI interaction data and embeds proteins into a low-dimensionalEuclidean space, under the premise that connectivity informationcorresponds to Euclidean proximity, as in geometric-random graphs.We judge the sensitivity and specificity of the fit by computingthe area under the Receiver Operator Characteristic (ROC) curve.The network embedding algorithm is based on multi-dimensionalscaling, with the square root of the path length in a networkplaying the role of the Euclidean distance in the Euclideanspace. The algorithm exploits sparsity for computational efficiency,and requires only a few sparse matrix multiplications, givinga complexity of O(N²) where N is the number of proteins. Results: The algorithm has been verified in the sense that itsuccessfully rediscovers the geometric structure in artificiallyconstructed geometric networks, even when noise is added byre-wiring some links. Applying the algorithm to 19 publiclyavailable PPI networks of various organisms indicated that:(a) geometric effects are present and (b) two-dimensional Euclideanspace is generally as effective as higher dimensional Euclideanspace for explaining the connectivity. Testing on a high-confidenceyeast data set produced a very strong indication of geometricstructure (area under the ROC curve of 0.89), with this networkbeing essentially indistinguishable from a noisy geometric network.Overall, the results add support to the hypothesis that PPInetworks have a geometric structure. Availability: MATLAB code implementing the algorithm is availableupon request. Contact: natasha{at}ics.uci.edu Associate Editor: Olga Troyanskaya     

PPO: predictor for prokaryotic operons

SUMMARY: We present an operon predictor for prokaryotic operons (PPO), which can predict operons in the entire prokaryotic genome. The prediction algorithm used in PPO allows the user to select binary particle swarm optimization (BPSO), a genetic algorithm (GA) or some other methods introduced in the literature to predict operons. The operon predictor on our web server and the provided database are easy to access and use. The main features offered are: (i) selection of the prediction algorithm; (ii) adjustable parameter settings of the prediction algorithm; (iii) graphic visualization of results; (iv) integrated database queries; (v) listing of experimentally verified operons; and (vi) related tools. Availability and implementation: PPO is freely available at http://bio.kuas.edu.tw/PPO/.     

A new algorithm for cluster analysis of genomic methylation: the Helicobacter pylori case

Motivation: The genomic methylation analysis is useful to typebacteria that have a high number of expressed type II methyltransferases.Methyltransferases are usually committed to Restriction andModification (R-M) systems, in which the restriction endonucleaseimposes high pressure on the expression of the cognate methyltransferasethat hinder R-M system loss. Conventional cluster methods donot reflect this tendency. An algorithm was developed for dendrogramconstruction reflecting the propensity for conservation of R-MType II systems. Results: The new algorithm was applied to 52 Helicobacter pyloristrains from different geographical regions and compared withconventional clustering methods. The algorithm works by firstgrouping strains that share a common minimum set of R-M systemsand gradually adds strains according to the number of the R-Msystems acquired. Dendrograms revealed a cluster of Africanstrains, which suggest that R-M systems are present in H.pylorigenome since its human host migrates from Africa. Availability: The software files are available at http://www.ff.ul.pt/paginas/jvitor/Bioinformatics/MCRM_algorithm.zip Contact: filipavale{at}fe.ucp.pt Supplementary information: Supplementary data are availableat Bioinformatics online. Associate Editor: Martin Bishop     

Observation of multiple folding pathways of beta-hairpin trpzip2 from independent continuous folding trajectories

Motivation: After 10-year investigations, the folding mechanismsof β-hairpins are still under debate. Experiments stronglysupport zip-out pathway, while most simulations prefer the hydrophobiccollapse model (including middle-out and zip-in pathways). Inthis article, we show that all pathways can occur during thefolding of β-hairpins but with different probabilities.The zip-out pathway is the most probable one. This is in agreementwith the experimental results. We came to our conclusions by38 100-ns room-temperature all-atom molecular dynamics simulationsof the β-hairpin trpzip2. Our results may help to clarifythe inconsistencies in the current pictures of β-hairpinfolding mechanisms. Contact: yxiao{at}mail.hust.edu.cn Supplementary information: Supplementary data are availableat Bioinformatics online. Associate Editor: Anna Tramontano     

Model-based deconvolution of genome-wide DNA binding

Motivation: Chromatin immunoprecipitation followed by hybridizationto a genomic tiling microarray (ChIP-chip) is a routinely usedprotocol for localizing the genomic targets of DNA-binding proteins.The resolution to which binding sites in this assay can be identifiedis commonly considered to be limited by two factors: (1) theresolution at which the genomic targets are tiled in the microarrayand (2) the large and variable lengths of the immunoprecipitatedDNA fragments. Results: We have developed a generative model of binding sitesin ChIP-chip data and an approach, MeDiChI, for efficientlyand robustly learning that model from diverse data sets. Wehave evaluated MeDiChI's performance using simulated data, aswell as on several diverse ChIP-chip data sets collected onwidely different tiling array platforms for two different organisms(Saccharomyces cerevisiae and Halobacterium salinarium NRC-1).We find that MeDiChI accurately predicts binding locations toa resolution greater than that of the probe spacing, even foroverlapping peaks, and can increase the effective resolutionof tiling array data by a factor of 5x or better. Moreover,the method's performance on simulated data provides insightsinto effectively optimizing the experimental design for increasedbinding site localization accuracy and efficacy. Availability: MeDiChI is available as an open-source R package,including all data, from http://baliga.systemsbiology.net/medichi. Contact: dreiss{at}systemsbiology.org Supplementary information: Supplementary data are availableat Bioinformatics online. Associate Editor: Martin Bishop     

Operon prediction by comparative genomics: an application to the Synechococcus sp. WH8102 genome

We present a computational method for operon prediction based on a comparative genomics approach. A group of consecutive genes is considered as a candidate operon if both their gene sequences and functions are conserved across several phylogenetically related genomes. In addition, various supporting data for operons are also collected through the application of public domain computer programs, and used in our prediction method. These include the prediction of conserved gene functions, promoter motifs and terminators. An apparent advantage of our approach over other operon prediction methods is that it does not require many experimental data (such as gene expression data and pathway data) as input. This feature makes it applicable to many newly sequenced genomes that do not have extensive experimental information. In order to validate our prediction, we have tested the method on Escherichia coli K12, in which operon structures have been extensively studied, through a comparative analysis against Haemophilus influenzae Rd and Salmonella typhimurium LT2. Our method successfully predicted most of the 237 known operons. After this initial validation, we then applied the method to a newly sequenced and annotated microbial genome, Synechococcus sp. WH8102, through a comparative genome analysis with two other cyanobacterial genomes, Prochlorococcus marinus sp. MED4 and P.marinus sp. MIT9313. Our results are consistent with previously reported results and statistics on operons in the literature.     

Systematic construction of gene coexpression networks with applications to human T helper cell differentiation process

Motivation: Coexpression networks have recently emerged as anovel holistic approach to microarray data analysis and interpretation.Choosing an appropriate cutoff threshold, above which a gene–geneinteraction is considered as relevant, is a critical task inmost network-centric applications, especially when two or morenetworks are being compared. Results: We demonstrate that the performance of traditionalapproaches, which are based on a pre-defined cutoff or significancelevel, can vary drastically depending on the type of data andapplication. Therefore, we introduce a systematic procedurefor estimating a cutoff threshold of coexpression networks directlyfrom their topological properties. Both synthetic and real datasetsshow clear benefits of our data-driven approach under variouspractical circumstances. In particular, the procedure providesa robust estimate of individual degree distributions, even frommultiple microarray studies performed with different array platformsor experimental designs, which can be used to discriminate thecorresponding phenotypes. Application to human T helper celldifferentiation process provides useful insights into the componentsand interactions controlling this process, many of which wouldhave remained unidentified on the basis of expression changealone. Moreover, several human–mouse orthologs showedconserved topological changes in both systems, suggesting theirpotential importance in the differentiation process. Contact: laliel{at}utu.fi Supplementary information: Supplementary data are availableat Bioinformatics online. Associate Editor: David Rocke     

基于迭代自学习的操纵子结构预测

原核生物操纵子结构的准确注释对基因功能和基因调控网络的研究具有重要意义,通过生物信息学方法计算预测是当前基因组操纵子结构注释的最主要来源.当前的预测算法大都需要实验确认的操纵子作为训练集,但实验确认的操纵子数据的缺乏一直成为发展算法的瓶颈.基于对操纵子结构的认识,从基因间距离、转录翻译相关的调控信号以及COG功能注释等特征出发,建立了描述操纵子复杂结构的概率模型,并提出了不依赖于特定物种操纵子数据作为训练集的迭代自学习算法.通过对实验验证的操纵子数据集的测试比较,结果表明算法对于预测操纵子结构非常有效.在不依赖于任何已知操纵子信息的情况下,算法在总体预测水平上超过了目前最好的操纵子预测方法,而且这种自学习的预测算法要优于依赖特定物种进行训练的算法.这些特点使得该算法能够适用于新测序的物种,有别于当前常用的操纵子预测方法.对细菌和古细菌的基因组进行大规模比较分析,进一步提高了对基因组操纵子结构的普遍特征和物种特异性的认识.     

A comprehensive assessment of sequence-based and template-based methods for protein contact prediction

Motivation: Pair-wise residue-residue contacts in proteins canbe predicted from both threading templates and sequence-basedmachine learning. However, most structure modeling approachesonly use the template-based contact predictions in guiding thesimulations; this is partly because the sequence-based contactpredictions are usually considered to be less accurate thanthat by threading. With the rapid progress in sequence databasesand machine-learning techniques, it is necessary to have a detailedand comprehensive assessment of the contact-prediction methodsin different template conditions. Results: We develop two methods for protein-contact predictions:SVM-SEQ is a sequence-based machine learning approach whichtrains a variety of sequence-derived features on contact maps;SVM-LOMETS collects consensus contact predictions from multiplethreading templates. We test both methods on the same set of554 proteins which are categorized into ‘Easy’,‘Medium’, ‘Hard’ and ‘Very Hard’targets based on the evolutionary and structural distance betweentemplates and targets. For the Easy and Medium targets, SVM-LOMETSobviously outperforms SVM-SEQ; but for the Hard and Very Hardtargets, the accuracy of the SVM-SEQ predictions is higher thanthat of SVM-LOMETS by 12–25%. If we combine the SVM-SEQand SVM-LOMETS predictions together, the total number of correctlypredicted contacts in the Hard proteins will increase by morethan 60% (or 70% for the long-range contact with a sequenceseparation 24), compared with SVM-LOMETS alone. The advantageof SVM-SEQ is also shown in the CASP7 free modeling targetswhere the SVM-SEQ is around four times more accurate than SVM-LOMETSin the long-range contact prediction. These data demonstratethat the state-of-the-art sequence-based contact predictionhas reached a level which may be helpful in assisting tertiarystructure modeling for the targets which do not have close structuretemplates. The maximum yield should be obtained by the combinationof both sequence- and template-based predictions. Contact: yzhang{at}ku.edu Supplementary information: Supplementary data are availableat Bioinformatics online. Associate Editor: Anna Tramontano     

Combining multiple positive training sets to generate confidence scores for protein-protein interactions

Motivation: High-throughput experimental and computational methodsare generating a wealth of protein–protein interactiondata for a variety of organisms. However, data produced by currentstate-of-the-art methods include many false positives, whichcan hinder the analyses needed to derive biological insights.One way to address this problem is to assign confidence scoresthat reflect the reliability and biological significance ofeach interaction. Most previously described scoring methodsuse a set of likely true positives to train a model to scoreall interactions in a dataset. A single positive training set,however, may be biased and not representative of true interactionspace. Results: We demonstrate a method to score protein interactionsby utilizing multiple independent sets of training positivesto reduce the potential bias inherent in using a single trainingset. We used a set of benchmark yeast protein interactions toshow that our approach outperforms other scoring methods. Ourapproach can also score interactions across data types, whichmakes it more widely applicable than many previously proposedmethods. We applied the method to protein interaction data fromboth Drosophila melanogaster and Homo sapiens. Independent evaluationsshow that the resulting confidence scores accurately reflectthe biological significance of the interactions. Contact: rfinley{at}wayne.edu Supplementary information: Supplementary data are availableat Bioinformatics Online. Associate Editor: Burkhard Rost     

3D-Garden: a system for modelling protein-protein complexes based on conformational refinement of ensembles generated with the marching cubes algorithm

Motivation: Reliable structural modelling of protein–proteincomplexes has widespread application, from drug design to advancingour knowledge of protein interactions and function. This workaddresses three important issues in protein–protein docking:implementing backbone flexibility, incorporating prior indicationsfrom experiment and bioinformatics, and providing public accessvia a server. 3D-Garden (Global And Restrained Docking ExplorationNexus), our benchmarked and server-ready flexible docking system,allows sophisticated programming of surface patches by the uservia a facet representation of the interactors’ molecularsurfaces (generated with the marching cubes algorithm). Flexibilityis implemented as a weighted exhaustive conformer search foreach clashing pair of molecular branches in a set of 5000 modelsfiltered from around 340 000 initially. Results: In a non-global assessment, carried out strictly accordingto the protocols for number of models considered and model qualityof the Critical Assessment of Protein Interactions (CAPRI) experiment,over the widely-used Benchmark 2.0 of 84 complexes, 3D-Gardenidentifies a set of ten models containing an acceptable or bettermodel in 29/45 test cases, including one with large conformationalchange. In 19/45 cases an acceptable or better model is rankedfirst or second out of 340 000 candidates. Availability: http://www.sbg.bio.ic.ac.uk/3dgarden (server) Contact: v.lesk{at}ic.ac.uk Supplementary information: Supplementary data are availableat Bioinformatics online. Associate Editor: Burkhard Rost