Search

Cyanobacteria of the Synechococcus and Prochlorococcus genera are important contributors to photosynthetic productivity in the open oceans (1-3). Recently, core photosystem II (PSII) genes were identified in cyanophages and proposed [...]

Discrete simulations of genetic regulatory networks have been used to study subsystems of yeast successfully. Existing models underling these simulations are based on specific transition functions, which determine the node states in the network. However, implementations of existing models are not freely available and support only a textual user interface (TUI). Additionally, even if an implementation that supports a graphic user interface (GUI) were available, the computations necessary to analyze the simulations would still have to be done manually. Furthermore, the usage of different transition functions by existing models suggests that an enriched model is needed. We developed a software tool, called GRegNetSim, that allows the end-user (a biologist) to describe genetic regulatory networks graphically. The input is displayed visually via Cytoscape (an open-source platform for the representation and analysis of biological networks). The user can specify various transition functions at different nodes of the network, supporting, for example, threshold and gradient effects, thereby analyzing the network under a variety of modes dictated by these functions. GRegNetSim displays the relationship between the inputs and the mode of behavior of the network in a graphic form that is easy to interpret. Furthermore, it automatically extracts statistical data such as the percentage of simulations that reached a steady state or the percentage of simulations that terminated with a certain state. The discrete simulations performed by GRegNetSim can be used to elucidate and predict the behavior, structure, and properties of genetic regulatory networks in a unified manner. GRegNetSim is implemented as a Cytoscape App. Installation files, examples, and source code, along with a detailed user guide, are freely available at https://sites.google.com/site/gregnetsim/. [ABSTRACT FROM AUTHOR]

We study the Partial Information Network Query (PINQ) problem, which generalizes two problems that often arise in bioinformatics: the Alignment Network Query (ANQ) problem and the Topology-Free Network Query (TFNQ) problem. In both ANQ and TFNQ we have a pattern P and a graph H , and we seek a subgraph of H that resembles P . ANQ requires knowing the topology of P , while TFNQ ignores it. PINQ fits the scenario where partial information is available on the topology of P . Our main result is a parameterized algorithm that handles inputs for PINQ in which P is a set of trees. This algorithm significantly improves the best known O ⁎ running time in solving TFNQ. We also improve the best known O ⁎ running times in solving two special cases of ANQ. [ABSTRACT FROM AUTHOR]

In this article we address two pattern matching problems which have important applications to bioinformatics. First we address the topology-free network query problem: Given a set of labels L, a multiset P of labels from L, a graph H = (V H, E H) and a function L a b e l H : V H → 2 L, we need to find a subtree S of H which is an occurrence of P. We provide a parameterized algorithm with parameter k = | P | that runs in time O * (2 k) and whose space complexity is polynomial. We also consider three variants of this problem. Then we address the alignment network query problem: Given two labeled graphs P and H, we need to find a subgraph S of H whose alignment with P is the best among all such subgraphs. We present two algorithms for cases in which P and H belong to certain families of DAGs. Their running times are polynomial and they are less restrictive than algorithms that are available today for alignment network queries. Topology-free and alignment network queries provide means to study the function and evolution of biological networks, and today, with the increasing amount of knowledge regarding biological networks, they are extremely relevant. [ABSTRACT FROM AUTHOR]

Background: Bench biologists often do not take part in the development of computational models for their systems, and therefore, they frequently employ them as "black-boxes". Our aim was to construct and test a model that does not depend on the availability of quantitative data, and can be directly used without a need for intensive computational background. Results: We present a discrete transition model. We used cell-cycle in budding yeast as a paradigm for a complex network, demonstrating phenomena such as sequential protein expression and activity, and cell-cycle oscillation. The structure of the network was validated by its response to computational perturbations such as mutations, and its response to mating-pheromone or nitrogen depletion. The model has a strong predicative capability, demonstrating how the activity of a specific transcription factor, Hcm1, is regulated, and what determines commitment of cells to enter and complete the cell-cycle. Conclusion: The model presented herein is intuitive, yet is expressive enough to elucidate the intrinsic structure and qualitative behavior of large and complex regulatory networks. Moreover our model allowed us to examine multiple hypotheses in a simple and intuitive manner, giving rise to testable predictions. This methodology can be easily integrated as a useful approach for the study of networks, enriching experimental biology with computational insights [ABSTRACT FROM AUTHOR]

Background: Monocytes, which are key players in innate immunity, are outnumbered by neutrophils and lymphocytes among peripheral white blood cells. The cytokine interferon-β (IFN-β) is widely used as an immunomodulatory drug for multiple sclerosis and its functional pathways in peripheral blood mononuclear cells (PBMCs) have been previously described. The aim of the present study was to identify novel, cell-specific IFN-β functions and pathways in tumor necrosis factor (TNF)-α-activated monocytes that may have been missed in studies using PBMCs. Methodology/Principal Findings: Whole genome gene expression profiles of human monocytes and T cells were compared following in vitro priming to TNF-α and overnight exposure to IFN-β. Statistical analyses of the gene expression data revealed a cell-type-specific change of 699 transcripts, 667 monocyte-specific transcripts, 21 T cell-specific transcripts and 11 transcripts with either a difference in the response direction or a difference in the magnitude of response. RT-PCR revealed a set of differentially expressed genes (DEGs), exhibiting responses to IFN-β that are modulated by TNF-α in monocytes, such as RIPK2 and CD83, but not in T cells or PBMCs. Known IFN-β promoter response elements, such as ISRE, were enriched in T cell DEGs but not in monocyte DEGs. The overall directionality of the gene expression regulation by IFN-β was different in T cells and monocytes, with up-regulation more prevalent in T cells, and a similar extent of up and down-regulation recorded in monocytes. Conclusions: By focusing on the response of distinct cell types and by evaluating the combined effects of two cytokines with pro and anti-inflammatory activities, we were able to present two new findings First, new IFN-β response pathways and genes, some of which were monocytes specific; second, a cell-specific modulation of the IFN-β response transcriptome by TNF-α. [ABSTRACT FROM AUTHOR]

Viral genomes often contain genes recently acquired from microbes. In some cases (for example, psbA) the proteins encoded by these genes have been shown to be important for viral replication. In this study, using a unique search strategy on the Global Ocean Survey (GOS) metagenomes in combination with marine virome and microbiome pyrosequencing-based datasets, we characterize previously undetected microbial metabolic capabilities concealed within the genomes of uncultured marine viral communities. A total of 34 microbial gene families were detected on 452 viral GOS scaffolds. The majority of auxiliary metabolic genes found on these scaffolds have never been reported in phages. Host genes detected in viruses were mainly divided between genes encoding for different energy metabolism pathways, such as electron transport and newly identified photosystem genes, or translation and post-translation mechanism related. Our findings suggest previously undetected ways, in which marine phages adapt to their hosts and improve their fitness, including translation and post-translation level control over the host rather than the already known transcription level control. [ABSTRACT FROM AUTHOR]

Background: Pathways provide topical descriptions of cellular circuitry. Comparing analogous pathways reveals intricate insights into individual functional differences among species. While previous works in the field performed genomic comparisons and evolutionary studies that were based on specific genes or proteins, whole genomic sequence, or even single pathways, none of them described a genomic system level comparative analysis of metabolic pathways. In order to properly implement such an analysis one should overcome two specific challenges: how to combine the effect of many pathways under a unified framework and how to appropriately analyze co-evolution of pathways. Here we present a computational approach for solving these two challenges. First, we describe a comprehensive, scalable, information theory based computational pipeline that calculates pathway alignment information and then compiles it in a novel manner that allows further analysis. This approach can be used for building phylogenies and for pointing out specific differences that can then be analyzed in depth. Second, we describe a new approach for comparing the evolution of metabolic pathways. This approach can be used for detecting co-evolutionary relationships between metabolic pathways. Results: We demonstrate the advantages of our approach by applying our pipeline to data from the MetaCyc repository (which includes a total of 205 organisms and 660 metabolic pathways). Our analysis revealed several surprising biological observations. For example, we show that the different habitats in which Archaea organisms reside are reflected by a pathway based phylogeny. In addition, we discover two striking clusters of metabolic pathways, each cluster includes pathways that have very similar evolution. Conclusion: We demonstrate that distance measures that are based on the topology and the content of metabolic networks are useful for studying evolution and co-evolution. [ABSTRACT FROM AUTHOR]

Abstract: Given two undirected trees T and P, the Subtree Homeomorphism Problem is to find whether T has a subtree t that can be transformed into P by removing entire subtrees, as well as repeatedly removing a degree-2 node and adding the edge joining its two neighbors. In this paper we extend the Subtree Homeomorphism Problem to a new optimization problem by enriching the subtree-comparison with node-to-node similarity scores. The new problem, called Approximate Labelled Subtree Homeomorphism (ALSH), is to compute the homeomorphic subtree of T which also maximizes the overall node-to-node resemblance. We describe an algorithm for solving ALSH on unordered, unrooted trees, where m and n are the number of vertices in P and T, respectively. We also give an algorithm for rooted ordered trees and and algorithms for unrooted cyclically ordered and unrooted linearly ordered trees, respectively. [Copyright &y& Elsevier]

Abstract: Consider a matrix with columns , and rows R, or—equivalently—a hypergraph having M as its adjacency matrix (where R are the vertices and C are the hyperedges). Denote and . We consider the following two problems: (a) Is there a graph H, with vertex set C, such that every vertex subgraph of H is a tree and the intersection of every two such trees is also a tree? (b) Is there a graph H, with vertex set C, such that every is a unicycle and the intersection of every two and every three unicycles is a tree? These questions occur in application areas such as database management systems and computational biology; e.g., in the latter they arise in the context of the analysis of biological networks, primarily for the purpose of data clustering. We describe algorithms to find such intersection representations of a matrix M (and equivalently of the hypergraph M), when they exist. [Copyright &y& Elsevier]

We present MAGIC, an integrative and accurate method for comparative genome mapping. Our method consists of two phases: preprocessing for identifying "maximal similar segments," and mapping for clustering and classifying these segments. MAGIC's main novelty lies in its biologically intuitive clustering approach, which aims towards both calculating reorder-free segments and identifying orthologous segments. In the process, MAGIC efficiently handles ambiguities resulting from duplications that occurred before the speciation of the considered organisms from their most recent common ancestor. We demonstrate both MAGIC's robustness and scalability: the former is asserted with respect to its initial input and with respect to its parameters' values. The latter is asserted by applying MAGIC to distantly related organisms and to large genomes. We compare MAGIC to other comparative mapping methods and provide detailed analysis of the differences between them. Our improvements allow a comprehensive study of the diversity of genetic repertoires resulting from large-scale mutations, such as indels and duplications, including explicitly transposable and phagic elements. The strength of our method is demonstrated by detailed statistics computed for each type of these large-scale mutations. MAGIC enabled us to conduct a comprehensive analysis of the different forces shaping prokaryotic genomes from different clades, and to quantify the importance of novel gene content introduced by horizontal gene transfer relative to gene duplication in bacterial genome evolution. We use these results to investigate the breakpoint distribution in several prokaryotic genomes. [ABSTRACT FROM AUTHOR]

Abstract: A floorplan represents the relative relations between modules on an integrated circuit. Floorplans are commonly classified as slicing, mosaic, or general. Separable and Baxter permutations are classes of permutations that can be defined in terms of forbidden subsequences. It is known that the number of slicing floorplans equals the number of separable permutations and that the number of mosaic floorplans equals the number of Baxter permutations [B. Yao, H. Chen, C.K. Cheng, R.L. Graham, Floorplan representations: complexity and connections, ACM Trans. Design Automation Electron. Systems 8(1) (2003) 55–80]. We present a simple and efficient bijection between Baxter permutations and mosaic floorplans with applications to integrated circuits design. Moreover, this bijection has two additional merits: (1) It also maps between separable permutations and slicing floorplans; and (2) it suggests enumerations of mosaic floorplans according to various structural parameters. [Copyright &y& Elsevier]

Abstract: A guillotine partition of a -dimensional axis-aligned box is a recursive partition of by axis-aligned hyperplane cuts. The size of a guillotine partition is the number of boxes it contains. Two guillotine partitions are box-equivalent if their boxes satisfy compatible order relations with respect to the axes. (In many works, box-equivalent guillotine partitions are considered identical.) In the present work we define cut-equivalence of guillotine partitions, derived in a similar way from order relations of cuts. We prove structural properties related to these kinds of equivalence, and enumerate cut-equivalence classes of -dimensional guillotine partitions of size . [Copyright &y& Elsevier]

Abstract: We study the problem of sorting binary sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely for all , where ℓ is the length of the reversed subsequence. We present tight or nearly tight upper and lower bounds on the worst-case cost of sorting by reversals. Then we develop algorithms to approximate the optimal cost to sort a given input. Furthermore, we give polynomial-time algorithms to determine the optimal reversal sequence for a restricted but interesting class of sequences and cost functions. Our results have direct application in computational biology to the field of comparative genomics. [Copyright &y& Elsevier]

Abstract: Antifolates are used in the treatment of various human malignancies and exert their cytotoxic activity by inhibiting folate-dependent enzymes resulting in disruption of DNA synthesis and cell death. Here we devised a computerized hybrid functional petri nets (HFPN) modelling of folate metabolism under physiological and antifolate inhibitory conditions. This HFPN modelling proved valid as a good agreement was found between the simulated steady-state concentrations of various reduced folates and those published for cell extracts; consistently, the simulation derived total folate pool size (11.3μM) was identical to that published for cell extracts. In silico experiments were conducted to characterize the inhibitory profile of four distinct antifolates including methotrexate (MTX), tomudex, and LY309887, which inhibit dihydrofolate reductase (DHFR), thymidylate synthase (TS) and glycineamide ribonucleotide transformylase (GARTFase), respectively, as well as pemetrexed which has the capacity to inhibit all three enzymes. In order to assess the inhibitory activity of antifolates on purines and pyrimidines, the biosynthesis rates of IMP (20.53μM/min) and dTMP (23.8μM/min) were first simulated. Whereas the biochemical inhibitory profile of MTX was characterized by increased dihydrofolate and decreased tetrahydrofolate (THF) concentrations, the remaining antifolates did not decrease THF levels. Furthermore, MTX was 766- and 10-fold more potent in decreasing the production rates of IMP and dTMP, respectively, than pemetrexed. LY309887 indirectly decreased the rate of dTMP production by reducing the levels of 5-CH2-THF, a folate cofactor for TS. Surprisingly, pemetrexed failed to inhibit DHFR even at high concentrations. This HFPN-based simulation offers an inexpensive, user-friendly, rapid and reliable means of pre-clinical evaluation of the inhibitory profiles of antifolates. [Copyright &y& Elsevier]

Metagenomic data enables the study of microbes and viruses through their DNA as retrieved directly from the environment in which they live. Functional analysis of metagenomes explores the abundance of gene families, pathways, and systems, rather than their taxonomy. Through such analysis, researchers are able to identify those functional capabilities most important to organisms in the examined environment. Recently, a statistical framework for the functional analysis of metagenomes was described that focuses on gene families. Here we describe two pathway level computational models for functional analysis that take into account important, yet unaddressed issues such as pathway size, gene length, and overlap in gene content among pathways. We test our models over carefully designed simulated data and propose novel approaches for performance evaluation. Our models significantly improve over the current approach with respect to pathway ranking and the computations of relative abundance of pathways in environments.

Alternative splicing is regulated by splicing factors that serve as positive or negative effectors, interacting with regulatory elements along exons and introns. Here we present a novel computational method for genome-wide mapping of splicing factor binding sites that considers both the genomic environment and the evolutionary conservation of the regulatory elements. The method was applied to study the regulation of different alternative splicing events, uncovering an interesting network of interactions among splicing factors.

The optimal transformation of one tree into another by means of elementary edit operations is an important algorithmic problem that has several interesting applications to computational biology. Here we introduce a constrained form of this problem in which a partial mapping of a set of nodes (the "seeds") in one tree to a corresponding set of nodes in the other tree is given, and present efficient algorithms for both ordered and unordered trees. Whereas ordered tree matching based on seeded nodes has applications in pattern matching of RNA structures, unordered tree matching based on seeded nodes has applications in co-speciation and phylogeny reconciliation. The latter involves the solution of the planar tanglegram layout problem, for which a polynomial-time algorithm is given here.

A new problem in phylogenetic inference is presented, based on recent biological findings indicating a strong association between reversals (i.e., inversions) and repeats. These biological findings are formalized here in a new mathematical model, called repeat-annotated phylogenetic trees (RAPT). We show that, under RAPT, the evolutionary process--including both the tree-topology as well as internal node genome orders--is uniquely determined, a property that is of major significance both in theory and in practice. Furthermore, the repeats are employed to provide linear-time algorithms for reconstructing both the genomic orders and the phylogeny, which are NP-hard problems under the classical model of sorting by reversals (SBR).

Plant microRNAs (miRNAs) are short RNA sequences that bind to target mRNAs and change their expression levels by redirecting their stabilities and marking them for cleavage. In Arabidopsis thaliana, microRNAs have been shown to regulate development and are believed to impact expression both under various conditions, such as stress and stimuli, as well as in specific tissue types. We present a high throughput approach for associating between microRNAs and conditions in which they act, using novel statistical and algorithmic techniques. Our new tool, miRNAXpress, at first computes a (binary) matrix T denoting the potential targets of microRNAs. Then, using T and an additional predefined matrix X indicating expression of genes under various conditions, it produces a new matrix that predicts associations between microRNAs and the conditions in which they act. Thus, the program comprises two main modules that work in tandem to compute the desired output. The first is an efficient target prediction engine that predicts mRNA targets of query microRNAs by evaluating the optimal duplex that could be formed between the two: given a short query RNA, a long target RNA, and a predefined energy cut-off threshold, the program finds and reports all putative binding sites of the query RNA in the target RNA with hybridization energy bounded by the predefined threshold. The second module realizes an association operation that is computed by a method which relies on an efficient t-test to compute the associations. The calculation of the matrix of microRNAs and their potential targets is the computationally intensive part of the work done by miRNAXpress, and therefore an efficient algorithm for this portion facilitates the entire process. Thus, the target prediction engine is based on an efficient approximate hybridization search algorithm whose efficiency is the result of utilizing the sparsity of the search space without sacrificing the optimality of the results. The time complexity of this algorithm is almost linear in the size of a sparse set of locations where base-pairs are stacked at a height of three or more. Thus miRNAXpress is a novel tool for associating between microRNAs and the conditions in which they act. We employed it to conduct a study, using the plant Arabidopsis thaliana as our model organism. By applying miRNAXpress to 98 microRNAs and 380 conditions, some biologically interesting and statistically strong relations were discovered. For example, mir159C activity is possibly a factor in the misresponse of nph4 mutants to phototropic stimulations.

Current algorithmic studies of genome rearrangement ignore the length of reversals (or inversions); rather, they only count their number. We introduce a new cost model in which the lengths of the reversed sequences play a role, allowing more flexibility in accounting for mutation phenomena. Our focus is on sorting unsigned (unoriented) permutations by reversals; since this problem remains difficult (NP-hard) in our new model, the best we can hope for are approximation results. We propose an efficient, novel algorithm that takes (a monotonic function f of) length into account as an optimization criterion and study its properties. Our results include an upper bound of O(fn lg2n) for any additive cost measure f on the cost of sorting any n-element permutation, and a guaranteed approximation ratio of O(lg2n) times optimal for sorting a given permutation. Our work poses some interesting questions to both biologists and computer scientists and suggests some new bioinformatic insights that are currently being studied.