Gibbs process distinguishes survival and reveals contact-inhibition genes in Glioblastoma multiforme.

Tumor growth is a spatiotemporal birth-and-death process with loss of heterotypic contact-inhibition of locomotion (CIL) of tumor cells promoting invasion and metastasis. Therefore, representing tumor cells as two-dimensional points, we can expect the tumor tissues in histology slides to reflect realizations of spatial birth-and-death process which can be mathematically modeled to reveal molecular mechanisms of CIL, provided the mathematics models the inhibitory interactions. Gibbs process as an inhibitory point process is a natural choice since it is an equilibrium process of the spatial birth-and-death process. That is if the tumor cells maintain homotypic contact inhibition, the spatial distributions of tumor cells will result in Gibbs hard core process over long time scales. In order to verify if this is the case, we applied the Gibbs process to 411 TCGA Glioblastoma multiforme patient images. Our imaging dataset included all cases for which diagnostic slide images were available. The model revealed two groups of patients, one of which - the "Gibbs group," showed the convergence of the Gibbs process with significant survival difference. Further smoothing the discretized (and noisy) inhibition metric, for both increasing and randomized survival time, we found a significant association of the patients in the Gibbs group with increasing survival time. The mean inhibition metric also revealed the point at which the homotypic CIL establishes in tumor cells. Besides, RNAseq analysis between patients with loss of heterotypic CIL and intact homotypic CIL in the Gibbs group unveiled cell movement gene signatures and differences in Actin cytoskeleton and RhoA signaling pathways as key molecular alterations. These genes and pathways have established roles in CIL. Taken together, our integrated analysis of patient images and RNAseq data provides for the first time a mathematical basis for CIL in tumors, explains survival as well as uncovers the underlying molecular landscape for this key tumor invasion and metastatic phenomenon.

Hematopoietic Stem and Progenitor Cells Exhibit Stage-Specific Translational Programs via mTOR- and CDK1-Dependent Mechanisms.

Hematopoietic stem cells (HSCs) require highly regulated rates of protein synthesis, but it is unclear if they or lineage-committed progenitors preferentially recruit transcripts to translating ribosomes. We utilized polysome profiling, RNA sequencing, and whole-proteomic approaches to examine the translatome in LSK (Lin-Sca-1+c-Kit+) and myeloid progenitor (MP; Lin-Sca-1-c-Kit+) cells. Our studies show that LSKs exhibit low global translation but high translational efficiencies (TEs) of mRNAs required for HSC maintenance. In contrast, MPs activate translation in an mTOR-independent manner due, at least in part, to proteasomal degradation of mTOR by the E3 ubiquitin ligase c-Cbl. In the near absence of mTOR, CDK1 activates eIF4E-dependent translation in MPs through phosphorylation of 4E-BP1. Aberrant activation of mTOR expression and signaling in c-Cbl-deficient MPs results in increased mature myeloid lineage output. Overall, our data demonstrate that hematopoietic stem and progenitor cells (HSPCs) undergo translational reprogramming mediated by previously uncharacterized mechanisms of translational regulation.

Consensus on Molecular Subtypes of High-Grade Serous Ovarian Carcinoma.

Purpose: The majority of ovarian carcinomas are of high-grade serous histology, which is associated with poor prognosis. Surgery and chemotherapy are the mainstay of treatment, and molecular characterization is necessary to lead the way to targeted therapeutic options. To this end, various computational methods for gene expression-based subtyping of high-grade serous ovarian carcinoma (HGSOC) have been proposed, but their overlap and robustness remain unknown.Experimental Design: We assess three major subtype classifiers by meta-analysis of publicly available expression data, and assess statistical criteria of subtype robustness and classifier concordance. We develop a consensus classifier that represents the subtype classifications of tumors based on the consensus of multiple methods, and outputs a confidence score. Using our compendium of expression data, we examine the possibility that a subset of tumors is unclassifiable based on currently proposed subtypes.Results: HGSOC subtyping classifiers exhibit moderate pairwise concordance across our data compendium (58.9%-70.9%; P < 10-5) and are associated with overall survival in a meta-analysis across datasets (P < 10-5). Current subtypes do not meet statistical criteria for robustness to reclustering across multiple datasets (prediction strength < 0.6). A new subtype classifier is trained on concordantly classified samples to yield a consensus classification of patient tumors that correlates with patient age, survival, tumor purity, and lymphocyte infiltration.Conclusions: A new consensus ovarian subtype classifier represents the consensus of methods and demonstrates the importance of classification approaches for cancer that do not require all tumors to be assigned to a distinct subtype. Clin Cancer Res; 24(20); 5037-47. ©2018 AACR.

Public data and open source tools for multi-assay genomic investigation of disease.

Molecular interrogation of a biological sample through DNA sequencing, RNA and microRNA profiling, proteomics and other assays, has the potential to provide a systems level approach to predicting treatment response and disease progression, and to developing precision therapies. Large publicly funded projects have generated extensive and freely available multi-assay data resources; however, bioinformatic and statistical methods for the analysis of such experiments are still nascent. We review multi-assay genomic data resources in the areas of clinical oncology, pharmacogenomics and other perturbation experiments, population genomics and regulatory genomics and other areas, and tools for data acquisition. Finally, we review bioinformatic tools that are explicitly geared toward integrative genomic data visualization and analysis. This review provides starting points for accessing publicly available data and tools to support development of needed integrative methods.

Exactly computing the parsimony scores on phylogenetic networks using dynamic programming.

Scoring a given phylogenetic network is the first step that is required in searching for the best evolutionary framework for a given dataset. Using the principle of maximum parsimony, we can score phylogenetic networks based on the minimum number of state changes across a subset of edges of the network for each character that are required for a given set of characters to realize the input states at the leaves of the networks. Two such subsets of edges of networks are interesting in light of studying evolutionary histories of datasets: (i) the set of all edges of the network, and (ii) the set of all edges of a spanning tree that minimizes the score. The problems of finding the parsimony scores under these two criteria define slightly different mathematical problems that are both NP-hard. In this article, we show that both problems, with scores generalized to adding substitution costs between states on the endpoints of the edges, can be solved exactly using dynamic programming. We show that our algorithms require O(m(p)k) storage at each vertex (per character), where k is the number of states the character can take, p is the number of reticulate vertices in the network, m = k for the problem with edge set (i), and m = 2 for the problem with edge set (ii). This establishes an O(nm(p)k(2)) algorithm for both the problems (n is the number of leaves in the network), which are extensions of Sankoff's algorithm for finding the parsimony scores for phylogenetic trees. We will discuss improvements in the complexities and show that for phylogenetic networks whose underlying undirected graphs have disjoint cycles, the storage at each vertex can be reduced to O(mk), thus making the algorithm polynomial for this class of networks. We will present some properties of the two approaches and guidance on choosing between the criteria, as well as traverse through the network space using either of the definitions. We show that our methodology provides an effective means to study a wide variety of datasets.

Models of gene gain and gene loss for probabilistic reconstruction of gene content in the last universal common ancestor of life.

BACKGROUND: The problem of probabilistic inference of gene content in the last common ancestor of several extant species with completely sequenced genomes is: for each gene that is conserved in all or some of the genomes, assign the probability that its ancestral gene was present in the genome of their last common ancestor. RESULTS: We have developed a family of models of gene gain and gene loss in evolution, and applied the maximum-likelihood approach that uses phylogenetic tree of prokaryotes and the record of orthologous relationships between their genes to infer the gene content of LUCA, the Last Universal Common Ancestor of all currently living cellular organisms. The crucial parameter, the ratio of gene losses and gene gains, was estimated from the data and was higher in models that take account of the number of in-paralogs in genomes than in models that treat gene presences and absences as a binary trait. CONCLUSION: While the numbers of genes that are placed confidently into LUCA are similar in the ML methods and in previously published methods that use various parsimony-based approaches, the identities of genes themselves are different. Most of the models of either kind treat the genes found in many existing genomes in a similar way, assigning to them high probabilities of being ancestral ("high ancestrality"). The ML models are more likely than others to assign high ancestrality to the genes that are relatively rare in the present-day genomes.

Maximum Parsimony on Phylogenetic networks.

BACKGROUND: Phylogenetic networks are generalizations of phylogenetic trees, that are used to model evolutionary events in various contexts. Several different methods and criteria have been introduced for reconstructing phylogenetic trees. Maximum Parsimony is a character-based approach that infers a phylogenetic tree by minimizing the total number of evolutionary steps required to explain a given set of data assigned on the leaves. Exact solutions for optimizing parsimony scores on phylogenetic trees have been introduced in the past. RESULTS: In this paper, we define the parsimony score on networks as the sum of the substitution costs along all the edges of the network; and show that certain well-known algorithms that calculate the optimum parsimony score on trees, such as Sankoff and Fitch algorithms extend naturally for networks, barring conflicting assignments at the reticulate vertices. We provide heuristics for finding the optimum parsimony scores on networks. Our algorithms can be applied for any cost matrix that may contain unequal substitution costs of transforming between different characters along different edges of the network. We analyzed this for experimental data on 10 leaves or fewer with at most 2 reticulations and found that for almost all networks, the bounds returned by the heuristics matched with the exhaustively determined optimum parsimony scores. CONCLUSION: The parsimony score we define here does not directly reflect the cost of the best tree in the network that displays the evolution of the character. However, when searching for the most parsimonious network that describes a collection of characters, it becomes necessary to add additional cost considerations to prefer simpler structures, such as trees over networks. The parsimony score on a network that we describe here takes into account the substitution costs along the additional edges incident on each reticulate vertex, in addition to the substitution costs along the other edges which are common to all the branching patterns introduced by the reticulate vertices. Thus the score contains an in-built cost for the number of reticulate vertices in the network, and would provide a criterion that is comparable among all networks. Although the problem of finding the parsimony score on the network is believed to be computationally hard to solve, heuristics such as the ones described here would be beneficial in our efforts to find a most parsimonious network.

A polynomial-time algorithm computing lower and upper bounds of the rooted subtree prune and regraft distance.

Rooted, leaf-labeled trees are used in biology to represent hierarchical relationships of various entities, most notably the evolutionary history of molecules and organisms. Rooted Subtree Prune and Regraft (rSPR) operation is a tree rearrangement operation that is used to transform a tree into another tree that has the same set of leaf labels. The minimum number of rSPR operations that transform one tree into another is denoted by d(rSPR) and gives a measure of dissimilarity between the trees, which can be used to compare trees obtained by different approaches, or, in the context of phylogenetic analysis, to detect horizontal gene transfer events by finding incongruences between trees of different evolving characters. The problem of computing the exact d(rSPR) measure is NP-hard, and most algorithms resort to finding sequences of rSPR operations that are sufficient for transforming one tree into another, thereby giving upper bound heuristics for the distance. In this article, we present an O(n4) recursive algorithm D-Clust that gives both lower bound and upper bound heuristics for the distance between trees with n shared leaves and also gives a sequence of operations that transforms one tree into another. Our experiments on simulated pairs of trees containing up to 100 leaves showed that the two bounds are almost equal for small distances, thereby giving the nearly-precise actual value, and that the upper bound tends to be close to the upper bounds given by other approaches for all pairs of trees.

A low-polynomial algorithm for assembling clusters of orthologous groups from intergenomic symmetric best matches.

MOTIVATION: Identifying orthologous genes in multiple genomes is a fundamental task in comparative genomics. Construction of intergenomic symmetrical best matches (SymBets) and joining them into clusters is a popular method of ortholog definition, embodied in several software programs. Despite their wide use, the computational complexity of these programs has not been thoroughly examined. RESULTS: In this work, we show that in the standard approach of iteration through all triangles of SymBets, the memory scales with at least the number of these triangles, O(g(3)) (where g = number of genomes), and construction time scales with the iteration through each pair, i.e. O(g(6)). We propose the EdgeSearch algorithm that iterates over edges in the SymBet graph rather than triangles of SymBets, and as a result has a worst-case complexity of only O(g(3)log g). Several optimizations reduce the run-time even further in realistically sparse graphs. In two real-world datasets of genomes from bacteriophages (POGs) and Mollicutes (MOGs), an implementation of the EdgeSearch algorithm runs about an order of magnitude faster than the original algorithm and scales much better with increasing number of genomes, with only minor differences in the final results, and up to 60 times faster than the popular OrthoMCL program with a 90% overlap between the identified groups of orthologs. AVAILABILITY AND IMPLEMENTATION: C++ source code freely available for download at ftp.ncbi.nih.gov/pub/wolf/COGs/COGsoft/. SUPPLEMENTARY INFORMATION: Supplementary materials are available at Bioinformatics online.