Mutational processes shape cancer genomes, leaving characteristic marks that are termed signatures. The level of activity of each such process, or its signature exposure, provides important information on the disease, improving patient stratification and the prediction of drug response. Thus, there is growing interest in developing refitting methods that decipher those exposures. Previous work in this domain was unsupervised in nature, employing algebraic decomposition and probabilistic inference methods. Here we provide a supervised approach to the problem of signature refitting and show its superiority over current methods. Our method, SuRe, leverages a neural network model to capture correlations between signature exposures in real data. We show that SuRe outperforms previous methods on sparse mutation data from tumor type specific data sets, as well as pan-cancer data sets, with an increasing advantage as the data become sparser. We further demonstrate its utility in clinical settings.

There is a growing awareness that tumor-adjacent normal tissues used as control samples in cancer studies do not represent fully healthy tissues. Instead, they are intermediates between healthy tissues and tumors. The factors that contribute to the deviation of such control samples from healthy state include exposure to the tumor-promoting factors, tumor-related immune response, and other aspects of tumor microenvironment. Characterizing the relation between gene expression of tumor-adjacent control samples and tumors is fundamental for understanding roles of microenvironment in tumor initiation and progression, as well as for identification of diagnostic and prognostic biomarkers for cancers. To address the demand, we developed and validated TranNet, a computational approach that utilizes gene expression in matched control and tumor samples to study the relation between their gene expression profiles. TranNet infers a sparse weighted bipartite graph from gene expression profiles of matched control samples to tumors. The results allow us to identify predictors (potential regulators) of this transition. To our knowledge, TranNet is the first computational method to infer such dependencies. We applied TranNet to the data of several cancer types and their matched control samples from The Cancer Genome Atlas (TCGA). Many predictors identified by TranNet are genes associated with regulation by the tumor microenvironment as they are enriched in G-protein coupled receptor signaling, cell-to-cell communication, immune processes, and cell adhesion. Correspondingly, targets of inferred predictors are enriched in pathways related to tissue remodelling (including the epithelial-mesenchymal Transition (EMT)), immune response, and cell proliferation. This implies that the predictors are markers and potential stromal facilitators of tumor progression. Our results provide new insights into the relationships between tumor adjacent control sample, tumor and the tumor environment. Moreover, the set of predictors identified by TranNet will provide a valuable resource for future investigations.

This special issue of Bioinformatics serves as the proceedings of the biennial joint meeting of ISMB (29th annual conference on Intelligent Systems for Molecular Biology) and ECCB (20th European Conference on Computational Biology, which took place July 25–30, 2021). ISMB/ECCB is the leading international forum for presenting new research results, disseminating methods and techniques and facilitating discussions among leading researchers, practitioners and students in the field. In addition, ISMB is the flagship conference of the International Society for Computational Biology (ISCB). Due to the worldwide COVID-19 pandemic, the ISMB/ECCB 2021 meeting, initially intended to be held in Lyon, France, was for the second time run as a fully virtual conference. The organizers of the virtual meeting made the best effort to bridge time zones—enabling the global bioinformatics community to gather and fully participate in the meeting. The papers published in this volume were selected from 289 submitted full length papers featuring original research. The submitted papers where thoroughly reviewed with each paper receiving at least 3 reviews (3.9 reviews on average). For the review purpose, the submitted manuscripts were assigned to 1 of 10 scientific areas according to authors’ preference and research topic, allowing for minor adjustments to avoid conflicts of interest. In addition to selecting 1 of the 10 areas, the authors could also designate a particular Community of Special Interest (COSI; Table 1) that would provide the best forum for presentation of their paper. The 10 research areas covered a broad spectrum of topics (Table 2) and also included a special General Computational Biology area intended for submissions on emerging topics or for those manuscripts that did not fit well in other reviewing areas. Finally, the area of Bioinformatics Education made a return to this year’s ISMB/ECCB. COSI distribution of accepted ISMB/ECCB 2021 proceedings papers COSI distribution of accepted ISMB/ECCB 2021 proceedings papers Thematic areas of ISMB/ECCB 2021 Note. The table lists the Area Chairs for each theme, the number of reviewed papers, the number of accepted papers and the acceptance rate for each area. Thematic areas of ISMB/ECCB 2021 Note. The table lists the Area Chairs for each theme, the number of reviewed papers, the number of accepted papers and the acceptance rate for each area. The reviewing of the submissions was overseen by the Senior Program Committee (SPC), which included the Proceedings Chairs (this editorial’s authors) and Area Chairs (AC, listed in Table 2). Several of the ACs were nominated by COSIs or by the ISMB/ECCB Steering Committee. Members of SPC were responsible for recruiting Program Committee members. Reviewers (Program Committee members and subreviewers recruited by them) judged the papers based on the novelty of computational approaches, relevance of biological questions, importance of biological insights, clarity of presentation, correctness and completeness of the study and expected impact. After submitting their reviews, the reviewers had the opportunity to discuss the papers and refine the scores. Final acceptance decisions were made by the entire SPC. Throughout the reviewing process, we adopted a stringent policy against conflicts of interest. Submissions that had any link to an Area Chair were reassigned to a different Area. Care was taken not to assign papers to reviewers with a link either. The definition of link was explicitly defined as broad—including collaborators (present and past few years), same institution (present, past few years, planned future moves), family relations, advisees/advisors, as well as any personal conflicts that could cause the appearance of conflict of interest, or that could genuinely interfere with objective reviewing. Finally, as Proceedings Chairs, we refrained from submitting papers to the conference. Among the 289 submissions, 55 were accepted for presentation at ISMB/ECCB and publication in the Proceedings, conditioned on revisions properly addressing the comments of the reviewers. This year all 55 conditionally accepted papers were revised and subsequently judged to have properly addressed the concerns of the reviewers and were accepted for the conference proceedings, resulting in a 19% acceptance rate overall. The acceptance rates for individual areas are shown in Table 2. Accepted papers were assigned to COSIs based on the preferences of both authors and COSI organizers (Table 1). We are deeply grateful to the Area Chairs, the 514 members of the Program Committee and the 291 subreviewers for their outstanding efforts in conducting a thorough and timely review process. Their contribution is at the core of the scientific quality of the conference. We also thank Steven Leard, and Seth Munholland for their support, guidance and handling logistical questions and all the other members of the ISMB/ECCB Steering Committee for their expert advice and supervision. We also thank the team at Oxford University Press for producing these special proceedings volume. We also thank all the authors for submitting their work. These proceedings would not be possible without the scientific ingenuity of the contributors of all the papers. We recognize that, despite our best efforts, the selection process is necessarily imperfect, and some outstanding work will have been missed. Nonetheless, we hope that all authors received helpful feedback on their work. Finally, we want to thank all the keynote speakers, presenters and all conference participants. Thank you all for allowing this meeting and the whole ISMB/ECCB community to continue to thrive. T.M.P. is supported by the Intramural Research Program of the National Library of Medicine, NIH. C.D. is supported by the Swiss National Science Foundation grant 183723. Conflict of Interest: none declared.

SUMMARY: Large-scale data analysis in bioinformatics requires pipelined execution of multiple software. Generally each stage in a pipeline takes considerable computing resources and several workflow management systems (WMS), e.g. Snakemake, Nextflow, Common Workflow Language, Galaxy, etc. have been developed to ensure optimum execution of the stages across two invocations of the pipeline. However, when the pipeline needs to be executed with different settings of parameters, e.g. thresholds, underlying algorithms, etc. these WMS require significant scripting to ensure an optimal execution. We developed JUDI on top of DoIt, a Python based WMS, to systematically handle parameter settings based on the principles of database management systems. Using a novel modular approach that encapsulates a parameter database in each task and file associated with a pipeline stage, JUDI simplifies plug-and-play of the pipeline stages. For a typical pipeline with n parameters, JUDI reduces the number of lines of scripting required by a factor of O(n). With properly designed parameter databases, JUDI not only enables reproducing research under published values of parameters but also facilitates exploring newer results under novel parameter settings. AVAILABILITY AND IMPLEMENTATION: https://github.com/ncbi/JUDI. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Cancers arise as the result of somatically acquired changes in the DNA of cancer cells. However, in addition to the mutations that confer a growth advantage, cancer genomes accumulate a large number of somatic mutations resulting from normal DNA damage and repair processes as well as carcinogenic exposures or cancer related aberrations of DNA maintenance machinery. These mutagenic processes often produce characteristic mutational patterns called mutational signatures. The decomposition of a cancer genome's mutation catalog into mutations consistent with such signatures can provide valuable information about cancer etiology. However, the results from different decomposition methods are not always consistent. Hence, one needs to be able to not only decompose a patient's mutational profile into signatures but also establish the accuracy of such decomposition. RESULTS: We proposed two complementary ways of measuring confidence and stability of decomposition results and applied them to analyze mutational signatures in breast cancer genomes. We identified both very stable and highly unstable signatures, as well as signatures that previously have not been associated with breast cancer. We also provided additional support for the novel signatures. Our results emphasize the importance of assessing the confidence and stability of inferred signature contributions. AVAILABILITY AND IMPLEMENTATION: All tools developed in this paper have been implemented in an R package, called SignatureEstimation, which is available from https://www.ncbi.nlm.nih.gov/CBBresearch/Przytycka/index.cgi\#signatureestimation. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Motivation: Mutual exclusivity is a widely recognized property of many cancer drivers. Knowledge about these relationships can provide important insights into cancer drivers, cancer-driving pathways and cancer subtypes. It can also be used to predict new functional interactions between cancer driving genes and uncover novel cancer drivers. Currently, most of mutual exclusivity analyses are preformed focusing on a limited set of genes in part due to the computational cost required to rigorously compute P -values. Results: To reduce the computing cost and perform less restricted mutual exclusivity analysis, we developed an efficient method to estimate P -values while controlling the mutation rates of individual patients and genes similar to the permutation test. A comprehensive mutual exclusivity analysis allowed us to uncover mutually exclusive pairs, some of which may have relatively low mutation rates. These pairs often included likely cancer drivers that have been missed in previous analyses. More importantly, our results demonstrated that mutual exclusivity can also provide information that goes beyond the interactions between cancer drivers and can, for example, elucidate different mutagenic processes in different cancer groups. In particular, including frequently mutated, long genes such as TTN in our analysis allowed us to observe interesting patterns of APOBEC activity in breast cancer and identify a set of related driver genes that are highly predictive of patient survival. In addition, we utilized our mutual exclusivity analysis in support of a previously proposed model where APOBEC activity is the underlying process that causes TP53 mutations in a subset of breast cancer cases. Availability and Implementation: http://www.ncbi.nlm.nih.gov/CBBresearch/Przytycka/index.cgi#wesme. Contact: [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

The analysis of the mutational landscape of cancer, including mutual exclusivity and co-occurrence of mutations, has been instrumental in studying the disease. We hypothesized that exploring the interplay between co-occurrence, mutual exclusivity, and functional interactions between genes will further improve our understanding of the disease and help to uncover new relations between cancer driving genes and pathways. To this end, we designed a general framework, BeWith, for identifying modules with different combinations of mutation and interaction patterns. We focused on three different settings of the BeWith schema: (i) BeME-WithFun, in which the relations between modules are enriched with mutual exclusivity, while genes within each module are functionally related; (ii) BeME-WithCo, which combines mutual exclusivity between modules with co-occurrence within modules; and (iii) BeCo-WithMEFun, which ensures co-occurrence between modules, while the within module relations combine mutual exclusivity and functional interactions. We formulated the BeWith framework using Integer Linear Programming (ILP), enabling us to find optimally scoring sets of modules. Our results demonstrate the utility of BeWith in providing novel information about mutational patterns, driver genes, and pathways. In particular, BeME-WithFun helped identify functionally coherent modules that might be relevant for cancer progression. In addition to finding previously well-known drivers, the identified modules pointed to other novel findings such as the interaction between NCOR2 and NCOA3 in breast cancer. Additionally, an application of the BeME-WithCo setting revealed that gene groups differ with respect to their vulnerability to different mutagenic processes, and helped us to uncover pairs of genes with potentially synergistic effects, including a potential synergy between mutations in TP53 and the metastasis related DCC gene. Overall, BeWith not only helped us uncover relations between potential driver genes and pathways, but also provided additional insights on patterns of the mutational landscape, going beyond cancer driving mutations. Implementation is available at https://www.ncbi.nlm.nih.gov/CBBresearch/Przytycka/software/bewith.html.

This special issue of Bioinformatics serves as the proceedings of the 24th annual conference Intelligent Systems for Molecular Biology (ISMB), which took place in Orlando, Florida, July 8–12, 2016 ( http://www.iscb.org/ismb2016 ). ISMB 2016, the official conference of the International Society for Computational Biology (ISCB, http://www.iscb.org/ ), was accompanied by 11 Special Interest Group meetings of 1 or 2 days each, and two satellite meetings. Since its inception, ISMB has been the largest international conference in computational biology and bioinformatics. It is the leading forum in the field for presenting new research results, disseminating methods and techniques and facilitating discussions among leading researchers, practitioners and students in the field. The 42 papers in this volume were selected from 188 original submissions divided into 5 Themes and 11 associated Areas, collectively led by 10 Theme Chairs and 22 Area Chairs ( Tables 1 and 2 ). For each area, the Area Chairs selected an expert program committee for their subdiscipline and oversaw the reviewing process for that area in coordination with the corresponding Theme Chairs. By design, the Theme and Area Chairs included a mix of experienced individuals reappointed from previous years and experts newly recruited to ensure broad technical expertise and to promote inclusivity of various elements of the research community. In total, the review process involved the 10 Theme Chairs, the 22 Area Chairs, 331 program committee members and an additional 129 external reviewers recruited as sub-reviewers by program committee members. Table 2 provides a summary of the areas, Area Chairs and a summary of the reviews by area. The conference used a slightly streamlined two-tier review system—a continuation and refinement of a process that begun with ISMB/ECCB 2013 in an effort to better ensure thorough and fair reviewing. Under the revised process, each of the 188 submissions was first reviewed by at least three expert referees, with a subset receiving between four and six reviews, as needed. Consensus on each paper was reached through online discussion among reviewers, Area Chairs and Theme Chairs. Among the 188 submissions, 42 were accepted for publication conditionally on revisions properly addressing the comments of the reviewers. All revised versions were inspected by the corresponding Theme Chairs and Area Chairs, sometimes relying on additional assessments provided by the original reviewers. All 42 submissions were judged to have properly addressed the concerns of the reviewers and were accepted for the conference proceedings, resulting in an overall acceptance rate of 42/188 = 22.3%. We believe that this two-tier system, which is more reflective of typical multiround journal review procedures, provided a means of ensuring that only the highest quality original work was accepted within the tight timing constraints imposed by the conference scheduling. We thank all authors for submitting their work. These proceedings would simply not be possible without the scientific ingenuity of the contributors of all the papers. We recognize that the process is not perfect, and some outstanding work might have been rejected despite our best efforts. Nonetheless, we are hopeful that all authors received helpful feedback on their work and that most believe their submissions were judged fairly and diligently. In total, the two-tier review process involved 687 individual reviews. We are deeply grateful to the Theme Chairs and the Area Chairs, the members of the program committee and the external subreviewers for their outstanding efforts in conducting a thorough review process in just 3 months. Their contribution is at the core of the scientific quality of the conference. We also thank Steven Leard for his continuing support with the review process; the team at Oxford University Press for preparing this special proceedings volume; and all the other members of the ISMB Steering Committee for their expert advice and supervision. Complete list of Themes, Theme Chairs, and Areas associated with each Theme Complete list of Themes, Theme Chairs, and Areas associated with each Theme Complete list of Areas, Area Chairs, and submission statistics Complete list of Areas, Area Chairs, and submission statistics

Recent genome-wide analyses have uncovered a high accumulation of RNA polymerase II (Pol II) at the 5' end of genes. This elevated Pol II presence at promoters, referred to here as Poll II poising, is mainly (but not exclusively) attributed to temporal pausing of transcription during early elongation which, in turn, has been proposed to be a regulatory step for processes that need to be activated "on demand". Yet, the full genome-wide regulatory role of Pol II poising is yet to be delineated. To elucidate the role of Pol II poising in B cell activation, we compared Pol II profiles in resting and activated B cells. We found that while Pol II poised genes generally overlap functionally among different B cell states and correspond to the functional groups previously identified for other cell types, non-poised genes are B cell state specific. Focusing on the changes in transcription activity upon B cell activation, we found that the majority of such changes were from poised to non-poised state. The genes showing this type of transition were functionally enriched in translation, RNA processing and mRNA metabolic process. Interestingly, we also observed a transition from non-poised to poised state. Within this set of genes we identified several Immediate Early Genes (IEG), which were highly expressed in resting B cell and shifted from non-poised to poised state after B cell activation. Thus Pol II poising does not only mark genes for rapid expression in the future, but it is also associated with genes that are silenced after a burst of their expression. Finally, we performed comparative analysis of the presence of G4 motifs in the context of poised versus non-poised but active genes. Interestingly we observed a differential enrichment of these motifs upstream versus downstream of TSS depending on poising status. The enrichment of G4 sequence motifs upstream of TSS of non-poised active genes suggests a potential role of quadruplexes in expression regulation.

Cancer is now increasingly studied from the perspective of dysregulated pathways, rather than as a disease resulting from mutations of individual genes. A pathway-centric view acknowledges the heterogeneity between genomic profiles from different cancer patients while assuming that the mutated genes are likely to belong to the same pathway and cause similar disease phenotypes. Indeed, network-centric approaches have proven to be helpful for finding genotypic causes of diseases, classifying disease subtypes, and identifying drug targets. In this review, we discuss how networks can be used to help understand patient-to-patient variations and how one can leverage this variability to elucidate interactions between cancer drivers.

MOTIVATION: The data gathered by the Pan-Cancer initiative has created an unprecedented opportunity for illuminating common features across different cancer types. However, separating tissue-specific features from across cancer signatures has proven to be challenging. One of the often-observed properties of the mutational landscape of cancer is the mutual exclusivity of cancer driving mutations. Even though studies based on individual cancer types suggested that mutually exclusive pairs often share the same functional pathway, the relationship between across cancer mutual exclusivity and functional connectivity has not been previously investigated. RESULTS: We introduce a classification of mutual exclusivity into three basic classes: within tissue type exclusivity, across tissue type exclusivity and between tissue type exclusivity. We then combined across-cancer mutual exclusivity with interactions data to uncover pan-cancer dysregulated pathways. Our new method, Mutual Exclusivity Module Cover (MEMCover) not only identified previously known Pan-Cancer dysregulated subnetworks but also novel subnetworks whose across cancer role has not been appreciated well before. In addition, we demonstrate the existence of mutual exclusivity hubs, putatively corresponding to cancer drivers with strong growth advantages. Finally, we show that while mutually exclusive pairs within or across cancer types are predominantly functionally interacting, the pairs in between cancer mutual exclusivity class are more often disconnected in functional networks.

BACKGROUND: As a fundamental genomic element, meiotic recombination hotspot plays important roles in life sciences. Thus uncovering its regulatory mechanisms has broad impact on biomedical research. Despite the recent identification of the zinc finger protein PRDM9 and its 13-mer binding motif as major regulators for meiotic recombination hotspots, other regulators remain to be discovered. Existing methods for finding DNA sequence motifs of recombination hotspots often rely on the enrichment of co-localizations between hotspots and short DNA patterns, which ignore the cross-individual variation of recombination rates and sequence polymorphisms in the population. Our objective in this paper is to capture signals encoded in genetic variations for the discovery of recombination-associated DNA motifs. RESULTS: Recently, an algorithm called "LDsplit" has been designed to detect the association between single nucleotide polymorphisms (SNPs) and proximal meiotic recombination hotspots. The association is measured by the difference of population recombination rates at a hotspot between two alleles of a candidate SNP. Here we present an open source software tool of LDsplit, with integrative data visualization for recombination hotspots and their proximal SNPs. Applying LDsplit on SNPs inside an established 7-mer motif bound by PRDM9 we observed that SNP alleles preserving the original motif tend to have higher recombination rates than the opposite alleles that disrupt the motif. Running on SNP windows around hotspots each containing an occurrence of the 7-mer motif, LDsplit is able to guide the established motif finding algorithm of MEME to recover the 7-mer motif. In contrast, without LDsplit the 7-mer motif could not be identified. CONCLUSIONS: LDsplit is a software tool for the discovery of cis-regulatory DNA sequence motifs stimulating meiotic recombination hotspots by screening and narrowing down to hotspot associated SNPs. It is the first computational method that utilizes the genetic variation of recombination hotspots among individuals, opening a new avenue for motif finding. Tested on an established motif and simulated datasets, LDsplit shows promise to discover novel DNA motifs for meiotic recombination hotspots.

MOTIVATION: Systematic Evolution of Ligands by EXponential Enrichment (SELEX) represents a state-of-the-art technology to isolate single-stranded (ribo)nucleic acid fragments, named aptamers, which bind to a molecule (or molecules) of interest via specific structural regions induced by their sequence-dependent fold. This powerful method has applications in designing protein inhibitors, molecular detection systems, therapeutic drugs and antibody replacement among others. However, full understanding and consequently optimal utilization of the process has lagged behind its wide application due to the lack of dedicated computational approaches. At the same time, the combination of SELEX with novel sequencing technologies is beginning to provide the data that will allow the examination of a variety of properties of the selection process. RESULTS: To close this gap we developed, Aptamotif, a computational method for the identification of sequence-structure motifs in SELEX-derived aptamers. To increase the chances of identifying functional motifs, Aptamotif uses an ensemble-based approach. We validated the method using two published aptamer datasets containing experimentally determined motifs of increasing complexity. We were able to recreate the author's findings to a high degree, thus proving the capability of our approach to identify binding motifs in SELEX data. Additionally, using our new experimental dataset, we illustrate the application of Aptamotif to elucidate several properties of the selection process.

Complex diseases are caused by a combination of genetic and environmental factors. Uncovering the molecular pathways through which genetic factors affect a phenotype is always difficult, but in the case of complex diseases this is further complicated since genetic factors in affected individuals might be different. In recent years, systems biology approaches and, more specifically, network based approaches emerged as powerful tools for studying complex diseases. These approaches are often built on the knowledge of physical or functional interactions between molecules which are usually represented as an interaction network. An interaction network not only reports the binary relationships between individual nodes but also encodes hidden higher level organization of cellular communication. Computational biologists were challenged with the task of uncovering this organization and utilizing it for the understanding of disease complexity, which prompted rich and diverse algorithmic approaches to be proposed. We start this chapter with a description of the general characteristics of complex diseases followed by a brief introduction to physical and functional networks. Next we will show how these networks are used to leverage genotype, gene expression, and other types of data to identify dysregulated pathways, infer the relationships between genotype and phenotype, and explain disease heterogeneity. We group the methods by common underlying principles and first provide a high level description of the principles followed by more specific examples. We hope that this chapter will give readers an appreciation for the wealth of algorithmic techniques that have been developed for the purpose of studying complex diseases as well as insight into their strengths and limitations.

The intrinsic stochasticity of gene expression leads to cell-to-cell variations, noise, in protein abundance. Several processes, including transcription, translation, and degradation of mRNA and proteins, can contribute to these variations. Recent single cell analyses of gene expression in yeast have uncovered a general trend where expression noise scales with protein abundance. This trend is consistent with a stochastic model of gene expression where mRNA copy number follows the random birth and death process. However, some deviations from this basic trend have also been observed, prompting questions about the contribution of gene-specific features to such deviations. For example, recent studies have pointed to the TATA box as a sequence feature that can influence expression noise by facilitating expression bursts. Transcription-originated noise can be potentially further amplified in translation. Therefore, we asked the question of to what extent sequence features known or postulated to accompany translation efficiency can also be associated with increase in noise strength and, on average, how such increase compares to the amplification associated with the TATA box. Untangling different components of expression noise is highly nontrivial, as they may be gene or gene-module specific. In particular, focusing on codon usage as one of the sequence features associated with efficient translation, we found that ribosomal genes display a different relationship between expression noise and codon usage as compared to other genes. Within nonribosomal genes we found that sequence high codon usage is correlated with increased noise relative to the average noise of proteins with the same abundance. Interestingly, by projecting the data on a theoretical model of gene expression, we found that the amplification of noise strength associated with codon usage is comparable to that of the TATA box, suggesting that the effect of translation on noise in eukaryotic gene expression might be more prominent than previously appreciated.

The regulatory mechanism of recombination is a fundamental problem in genomics, with wide applications in genome wide association studies, birth-defect diseases, molecular evolution, cancer research, etc. In mammalian genomes, recombination events cluster into short genomic regions called ¡§recombination hotspots¡¨. Recently, a 13-mer motif enriched in hotspots is identified as a candidate cis-regulatory element of human recombination hotspots, moreover, a zinc finger protein, PRDM9, binds to this motif and is associated with variation of recombination phenotype in human and mouse genomes, thus is a trans-acting regulator of recombination hotspots. However, this pair of cis and trans-regulators covers only a fraction of hotspots, thus other regulators of recombination hotspots remain to be discovered. In this paper, we propose an approach to predicting additional trans-regulators from DNA-binding proteins by comparing their enrichment of binding sites in hotspots. Applying this approach on newly mapped mouse hotspots genome-wide, we confirmed that PRDM9 is a major trans-regulator of hotspots. In addition, a list of top candidate trans-regulators of mouse hotspots is reported. Using GO analysis we observed that the top genes are enriched with function of his tone modification, highlighting the epigenetic regulatory mechanisms of recombination hotspots.

In complex diseases, various combinations of genomic perturbations often lead to the same phenotype. On a molecular level, combinations of genomic perturbations are assumed to dys-regulate the same cellular pathways. Such a pathway-centric perspective is fundamental to understanding the mechanisms of complex diseases and the identification of potential drug targets. In order to provide an integrated perspective on complex disease mechanisms, we developed a novel computational method to simultaneously identify causal genes and dys-regulated pathways. First, we identified a representative set of genes that are differentially expressed in cancer compared to non-tumor control cases. Assuming that disease-associated gene expression changes are caused by genomic alterations, we determined potential paths from such genomic causes to target genes through a network of molecular interactions. Applying our method to sets of genomic alterations and gene expression profiles of 158 Glioblastoma multiforme (GBM) patients we uncovered candidate causal genes and causal paths that are potentially responsible for the altered expression of disease genes. We discovered a set of putative causal genes that potentially play a role in the disease. Combining an expression Quantitative Trait Loci (eQTL) analysis with pathway information, our approach allowed us not only to identify potential causal genes but also to find intermediate nodes and pathways mediating the information flow between causal and target genes. Our results indicate that different genomic perturbations indeed dys-regulate the same functional pathways, supporting a pathway-centric perspective of cancer. While copy number alterations and gene expression data of glioblastoma patients provided opportunities to test our approach, our method can be applied to any disease system where genetic variations play a fundamental causal role.

Dynamic molecular interactions play a central role in regulating the functioning of cells and organisms. The availability of experimentally determined large-scale cellular networks, along with other high-throughput experimental data sets that provide snapshots of biological systems at different times and conditions, is increasingly helpful in elucidating interaction dynamics. Here we review the beginnings of a new subfield within computational biology, one focused on the global inference and analysis of the dynamic interactome. This burgeoning research area, which entails a shift from static to dynamic network analysis, promises to be a major step forward in our ability to model and reason about cellular function and behavior.

SUMMARY: SimBoolNet is an open source Cytoscape plugin that simulates the dynamics of signaling transduction using Boolean networks. Given a user-specified level of stimulation to signal receptors, SimBoolNet simulates the response of downstream molecules and visualizes with animation and records the dynamic changes of the network. It can be used to generate hypotheses and facilitate experimental studies about causal relations and crosstalk among cellular signaling pathways. AVAILABILITY: SimBoolNet package (with manual) is freely available at http://www.ncbi.nlm.nih.gov/CBBresearch/Przytycka/SimBoolNet

Correction to Chakrabarti S, Lanczycki CJ, Panchenko AR, Przytycka TM, Thiessen PA and Bryant SH: State of the art: refinement of multiple sequence alignments. BMC Bioinformatics 2006, 7:499.

MOTIVATION: Analysis of expression quantitative trait loci (eQTL) significantly contributes to the determination of gene regulation programs. However, the discovery and analysis of associations of gene expression levels and their underlying sequence polymorphisms continue to pose many challenges. Methods are limited in their ability to illuminate the full structure of the eQTL data. Most rely on an exhaustive, genome scale search that considers all possible locus-gene pairs and tests the linkage between each locus and gene. RESULT: To analyze eQTLs in a more comprehensive and efficient way, we developed the Graph based eQTL Decomposition method (GeD) that allows us to model genotype and expression data using an eQTL association graph. Through graph-based heuristics, GeD identifies dense subgraphs in the eQTL association graph. By identifying eQTL association cliques that expose the hidden structure of genotype and expression data, GeD effectively filters out most locus-gene pairs that are unlikely to have significant linkage. We apply GeD on eQTL data from Plasmodium falciparum, the human malaria parasite, and show that GeD reveals the structure of the relationship between all loci and all genes on a whole genome level. Furthermore, GeD allows us to uncover additional eQTLs with lower FDR, providing an important complement to traditional eQTL analysis methods.

BACKGROUND: The identification and characterization of interacting domain pairs is an important step towards understanding protein interactions. In the last few years, several methods to predict domain interactions have been proposed. Understanding the power and the limitations of these methods is key to the development of improved approaches and better understanding of the nature of these interactions. RESULTS: Building on the previously published Parsimonious Explanation method (PE) to predict domain-domain interactions, we introduced a new Generalized Parsimonious Explanation (GPE) method, which (i) adjusts the granularity of the domain definition to the granularity of the input data set and (ii) permits domain interactions to have different costs. This allowed for preferential selection of the so-called "co-occurring domains" as possible mediators of interactions between proteins. The performance of both variants of the parsimony method are competitive to the performance of the top algorithms for this problem even though parsimony methods use less information than some of the other methods. We also examined possible enrichment of co-occurring domains and homo-domains among domain interactions mediating the interaction of proteins in the network. The corresponding study was performed by surveying domain interactions predicted by the GPE method as well as by using a combinatorial counting approach independent of any prediction method. Our findings indicate that, while there is a considerable propensity towards these special domain pairs among predicted domain interactions, this overrepresentation is significantly lower than in the iPfam dataset. CONCLUSION: The Generalized Parsimonious Explanation approach provides a new means to predict and study domain-domain interactions. We showed that, under the assumption that all protein interactions in the network are mediated by domain interactions, there exists a significant deviation of the properties of domain interactions mediating interactions in the network from that of iPfam data.

The centrality-lethality rule, which notes that high-degree nodes in a protein interaction network tend to correspond to proteins that are essential, suggests that the topological prominence of a protein in a protein interaction network may be a good predictor of its biological importance. Even though the correlation between degree and essentiality was confirmed by many independent studies, the reason for this correlation remains illusive. Several hypotheses about putative connections between essentiality of hubs and the topology of protein-protein interaction networks have been proposed, but as we demonstrate, these explanations are not supported by the properties of protein interaction networks. To identify the main topological determinant of essentiality and to provide a biological explanation for the connection between the network topology and essentiality, we performed a rigorous analysis of six variants of the genomewide protein interaction network for Saccharomyces cerevisiae obtained using different techniques. We demonstrated that the majority of hubs are essential due to their involvement in Essential Complex Biological Modules, a group of densely connected proteins with shared biological function that are enriched in essential proteins. Moreover, we rejected two previously proposed explanations for the centrality-lethality rule, one relating the essentiality of hubs to their role in the overall network connectivity and another relying on the recently published essential protein interactions model.

The topology of beta-sheets is defined by the pattern of hydrogen-bonded strand pairing. Therefore, predicting hydrogen bonded strand partners is a fundamental step towards predicting beta-sheet topology. At the same time, finding the correct partners is very difficult due to long range interactions involved in strand pairing. Additionally, patterns of amino acids involved, in beta-sheet formations are very general and therefore difficult to use for computational recognition of specific contacts between strands. In this work, we report a new strand pairing algorithm. To address above mentioned difficulties, our algorithm attempts to mimic elements of the folding process. Namely, in addition to ensuring that the predicted hydrogen bonded strand pairs satisfy basic global consistency constraints, it takes into account hypothetical folding pathways. Consistently with this view, introducing hydrogen bonds between a pair of strands changes the probabilities of forming hydrogen bonds between other pairs of strand. We demonstrate that this approach provides an improvement over previously proposed algorithms. We also compare the performance of this method to that of a global optimization algorithm that poses the problem as integer linear programming optimization problem and solves it using ILOG CPLEX package.

BACKGROUND: A widely-used approach for discovering functional and physical interactions among proteins involves phylogenetic profile comparisons (PPCs). Here, proteins with similar profiles are inferred to be functionally related under the assumption that proteins involved in the same metabolic pathway or cellular system are likely to have been co-inherited during evolution. RESULTS: Our experimentation with E. coli and yeast proteins with 16 different carefully composed reference sets of genomes revealed that the phyletic patterns of proteins in prokaryotes alone could be adequate enough to make reasonably accurate functional linkage predictions. A slight improvement in performance is observed on adding few eukaryotes into the reference set, but a noticeable drop-off in performance is observed with increased number of eukaryotes. Inclusion of most parasitic, pathogenic or vertebrate genomes and multiple strains of the same species into the reference set do not necessarily contribute to an improved sensitivity or accuracy. Interestingly, we also found that evolutionary histories of individual pathways have a significant affect on the performance of the PPC approach with respect to a particular reference set. For example, to accurately predict functional links in carbohydrate or lipid metabolism, a reference set solely composed of prokaryotic (or bacterial) genomes performed among the best compared to one composed of genomes from all three super-kingdoms; this is in contrast to predicting functional links in translation for which a reference set composed of prokaryotic (or bacterial) genomes performed the worst. We also demonstrate that the widely used random null model to quantify the statistical significance of profile similarity is incomplete, which could result in an increased number of false-positives. CONCLUSION: Contrary to previous proposals, it is not merely the number of genomes but a careful selection of informative genomes in the reference set that influences the prediction accuracy of the PPC approach. We note that the predictive power of the PPC approach, especially in eukaryotes, is heavily influenced by the primary endosymbiosis and subsequent bacterial contributions. The over-representation of parasitic unicellular eukaryotes and vertebrates additionally make eukaryotes less useful in the reference sets. Reference sets composed of highly non-redundant set of genomes from all three super-kingdoms fare better with pathways showing considerable vertical inheritance and strong conservation (e.g. translation apparatus), while reference sets solely composed of prokaryotic genomes fare better for more variable pathways like carbohydrate metabolism. Differential performance of the PPC approach on various pathways, and a weak positive correlation between functional and profile similarities suggest that caution should be exercised while interpreting functional linkages inferred from genome-wide large-scale profile comparisons using a single reference set.

MOTIVATION: Determining orthology relations among genes across multiple genomes is an important problem in the post-genomic era. Identifying orthologous genes can not only help predict functional annotations for newly sequenced or poorly characterized genomes, but can also help predict new protein-protein interactions. Unfortunately, determining orthology relation through computational methods is not straightforward due to the presence of paralogs. Traditional approaches have relied on pairwise sequence comparisons to construct graphs, which were then partitioned into putative clusters of orthologous groups. These methods do not attempt to preserve the non-transitivity and hierarchic nature of the orthology relation. RESULTS: We propose a new method, COCO-CL, for hierarchical clustering of homology relations and identification of orthologous groups of genes. Unlike previous approaches, which are based on pairwise sequence comparisons, our method explores the correlation of evolutionary histories of individual genes in a more global context. COCO-CL can be used as a semi-independent method to delineate the orthology/paralogy relation for a refined set of homologous proteins obtained using a less-conservative clustering approach, or as a refiner that removes putative out-paralogs from clusters computed using a more inclusive approach. We analyze our clustering results manually, with support from literature and functional annotations. Since our orthology determination procedure does not employ a species tree to infer duplication events, it can be used in situations when the species tree is unknown or uncertain. CONTACT: [email protected], [email protected] SUPPLEMENTARY INFORMATION: Supplementary materials are available at Bioinformatics online.

BACKGROUND: Accurate multiple sequence alignments of proteins are very important in computational biology today. Despite the numerous efforts made in this field, all alignment strategies have certain shortcomings resulting in alignments that are not always correct. Refinement of existing alignment can prove to be an intelligent choice considering the increasing importance of high quality alignments in large scale high-throughput analysis. RESULTS: We provide an extensive comparison of the performance of the alignment refinement algorithms. The accuracy and efficiency of the refinement programs are compared using the 3D structure-based alignments in the BAliBASE benchmark database as well as manually curated high quality alignments from Conserved Domain Database (CDD). CONCLUSION: Comparison of performance for refined alignments revealed that despite the absence of dramatic improvements, our refinement method, REFINER, which uses conserved regions as constraints performs better in improving the alignments generated by different alignment algorithms. In most cases REFINER produces a higher-scoring, modestly improved alignment that does not deteriorate the well-conserved regions of the original alignment.

The maximum agreement subtree problem is the following. Given two rooted trees whose leaves are drawn from the same set of items (e.g., species), find the largest subset of these items so that the portions of the two trees restricted to these items are isomorphic. We consider the case which occurs frequently in practice, i.e., the case when the trees are binary, and give an O(nlog n) time algorithm for this problem.

In a network of asynchronous processors, the cost to send a message can differ significantly from one communication link to another. In such a setting, it is desirable to factor the cost of links into the cost of distributed computation. Assume that associated with each link is a positive weight representing the cost of sending one message along the link, and the cost of an algorithm executed on a weighted network is the sum of the costs of all messages sent during its execution. We determine the asymptotic complexity of distributed leader election on a weighted unidirectional asynchronous ring assuming this notion of cost, by exhibiting a simple algorithm and a matching lower bound for the problem for any collection of edge weights. As a consequence, we see that algorithms designed for unweighted rings are not in general efficient for the weighted case.

This paper presents two sets of techniques for comparing unrooted evolutionary trees, namely, label compression and four-way dvnamic programming.The technique of four-way dynamic programming transforms existing algorithms for computing rooted maximum agree ment subtrees into new ones for unrooted trees.Let n be the size of the two input trees.This technique leads to an O(n log n)-time algorithm for unrooted trees whose degrees are bounded by a constant, matching the best known complexity for the rooted binary case.The technique of label compression is not based on dynamic programming.With this technique, we obtain an O(nl"5 log n)-time algorithm for unrooted trees with arbitrary degrees, also matching the best algorithm for the rooted unbounded degree case.

We present a parallel algorithm for the Huffman coding problem. We reduce the Huffman coding problem to the concave least weight subsequence (CLWS) problem and give a parallel algorithm that solves the latter problem in $O(\sqrt n \log n)$ time with n processors on a concurrent read exclusive write parameter random-access machine (CREW PRAM). This leads to the first sublinear-time $o(n^2 )$-total-work parallel algorithm for Huffman coding. This reduction of the Huffman coding problem to the CLWS problem also yields an alternative $O(n\log n)$-time (or linear-time, for a sorted input sequence) algorithm for Huffman coding.

In this paper, an $O(nL\log n)$-time algorithm is presented for construction of an optimal alphabetic binary tree with height restricted to L. This algorithm is an alphabetic version of the Package Merge algorithm, and yields an $O(nL\log n)$-time algorithm for the alphabetic Huffman coding problem. The Alphabetic Package Merge algorithm is quite simple to describe, but appears hard to prove correct. Garey [SIAM J Comput., 3 (1974), pp. 101–110] gives an $O(n^3 \log n)$-time algorithm for the height-limited alphabetic binary tree problem. Itai [SIAM J. Comput., 5 (1976), pp. 9–18] and Wessner [Inform. Process. Lett., 4 (1976), pp. 90–94] independently reduce this time to $O(n^2 L)$ for the alphabetic problem. In [SIAM J. Comput., 16 (1987), pp. 1115–1123], a rather complex $O(n^{{3 / 2}} L\log ^{{1 / 2}} n)$ -time “hybrid” algorithm is given for length-limited Huffman coding. The Package Merge algorithm, discussed in this paper, first appeared in [Tech. Report, 88-01, ICS Dept. Univ. of California, Irvine, CA], but without proof of correctness.

A parallel algorithm is given which constructs an optimal alphabetic tree in 0(log3 n) time with n2 log n processors.The construction is basically a paral.lelization of the Garsia-Wachs version [5] of the Hu-tucker algorithm [8].The best previous NC algorithm for the problem uses n6/ logo(l) n processors.[15] Our method is an extension of techniques used first in [3] and later used in [13] for the Huffman coding problem, which can be viewed as the alphabetic tree problem for the special case of a monotone weight sequence.In this paper, we extend to the cue of certain "almost monotone" sequences, which we call "sorted regular valleys.'The processing of such subsequences depends on a quadrangle inequality, while the total number of global iterations depends on a kind of tree contraction.Altogether we can view our algorithmic approach as (quadrangle inegualitg + tree contraction).An optimal alphabetic tree is a special case of an optimal binary search tree where all the weights are in the leaves.Thus, the result gives a partial answer to the open problem posed in [3]: is there an NC algorithm which can find an optimal binary search tree and which U*%S 7?6-t p9%s.7.3.2iTafvr Svme G > o? " This research was supported

Article Parallel construction of trees with optimal weighted path length Share on Authors: Lawrence L. Larmore Department of Computer Science, University of California, Riverside, CA Department of Computer Science, University of California, Riverside, CAView Profile , Teresa M. Przytycka Department of Computer Science, University of California, Riverside, CA and Instytut Informatyki, Uniwersytet Warszawski Department of Computer Science, University of California, Riverside, CA and Instytut Informatyki, Uniwersytet WarszawskiView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 71–80https://doi.org/10.1145/113379.113386Published:01 June 1991 10citation317DownloadsMetricsTotal Citations10Total Downloads317Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, a technique is developed that allows the construction of a triangulation of a closed orientable surface of genus g by an n-vertex graph in such a way that the triangulation does not have short noncontractible cycles. Using this technique, a counterexample is constructed to a conjecture by Hutchinson that the length of the shortest noncontractible cycle in any such triangulation is $O(\sqrt{n/g} )$. The presented technique can also be used to show that the function $\sqrt{n/g} \log^{ *} g$ provides a lower bound for the shortest noncontractible cycle in a triangulation of a surface of genus g.