Many disciplines, from human genetics and oncology to plant breeding, microbiology and virology, commonly face the challenge of analyzing rapidly increasing numbers of genomes. In case of Homo sapiens, the number of sequenced genomes will approach hundreds of thousands in the next few years. Simply scaling up established bioinformatics pipelines will not be sufficient for leveraging the full potential of such rich genomic data sets. Instead, novel, qualitatively different computational methods and paradigms are needed. We will witness the rapid extension of computational pan-genomics, a new sub-area of research in computational biology. In this article, we generalize existing definitions and understand a pan-genome as any collection of genomic sequences to be analyzed jointly or to be used as a reference. We examine already available approaches to construct and use pan-genomes, discuss the potential benefits of future technologies and methodologies and review open challenges from the vantage point of the above-mentioned biological disciplines. As a prominent example for a computational paradigm shift, we particularly highlight the transition from the representation of reference genomes as strings to representations as graphs. We outline how this and other challenges from different application domains translate into common computational problems, point out relevant bioinformatics techniques and identify open problems in computer science. With this review, we aim to increase awareness that a joint approach to computational pan-genomics can help address many of the problems currently faced in various domains.
Motivation: DNA sequencing of multiple samples from the same tumor provides data to analyze the process of clonal evolution in the population of cells that give rise to a tumor. Results: We formalize the problem of reconstructing the clonal evolution of a tumor using single-nucleotide mutations as the variant allele frequency (VAF) factorization problem. We derive a combinatorial characterization of the solutions to this problem and show that the problem is NP-complete. We derive an integer linear programming solution to the VAF factorization problem in the case of error-free data and extend this solution to real data with a probabilistic model for errors. The resulting AncesTree algorithm is better able to identify ancestral relationships between individual mutations than existing approaches, particularly in ultra-deep sequencing data when high read counts for mutations yield high confidence VAFs. Availability and implementation: An implementation of AncesTree is available at: http://compbio.cs.brown.edu/software. Contact:braphael@brown.edu Supplementary information: Supplementary data are available at Bioinformatics online.
Multiple immune factors control host responses to Mycobacterium tuberculosis infection, including the formation of granulomas, which are aggregates of immune cells whose function may reflect success or failure of the host to contain infection. One such factor is TNF-α. TNF-α has been experimentally characterized to have the following activities in M. tuberculosis infection: macrophage activation, apoptosis, and chemokine and cytokine production. Availability of TNF-α within a granuloma has been proposed to play a critical role in immunity to M. tuberculosis. However, in vivo measurement of a TNF-α concentration gradient and activities within a granuloma are not experimentally feasible. Further, processes that control TNF-α concentration and activities in a granuloma remain unknown. We developed a multiscale computational model that includes molecular, cellular, and tissue scale events that occur during granuloma formation and maintenance in lung. We use our model to identify processes that regulate TNF-α concentration and cellular behaviors and thus influence the outcome of infection within a granuloma. Our model predicts that TNF-αR1 internalization kinetics play a critical role in infection control within a granuloma, controlling whether there is clearance of bacteria, excessive inflammation, containment of bacteria within a stable granuloma, or uncontrolled growth of bacteria. Our results suggest that there is an interplay between TNF-α and bacterial levels in a granuloma that is controlled by the combined effects of both molecular and cellular scale processes. Finally, our model elucidates processes involved in immunity to M. tuberculosis that may be new targets for therapy.
Molecular simulation techniques are increasingly being used to study biomolecular systems at an atomic level. Such simulations rely on empirical force fields to represent the intermolecular interactions. There are many different force fields available—each based on a different set of assumptions and thus requiring different parametrization procedures. Recently, efforts have been made to fully automate the assignment of force-field parameters, including atomic partial charges, for novel molecules. In this work, we focus on a problem arising in the automated parametrization of molecules for use in combination with the gromos family of force fields: namely, the assignment of atoms to charge groups such that for every charge group the sum of the partial charges is ideally equal to its formal charge. In addition, charge groups are required to have size at most k. We show -hardness and give an exact algorithm that solves practical problem instances to provable optimality in a fraction of a second.
Cancer is characterized by intra-tumor heterogeneity, the presence of distinct cell populations with distinct complements of somatic mutations, which include single-nucleotide variants (SNVs) and copy-number aberrations (CNAs). Single-cell sequencing technology enables one to study these cell populations at single-cell resolution. Phylogeny estimation algorithms that employ appropriate evolutionary models are key to understanding the evolutionary mechanisms behind intra-tumor heterogeneity. We introduce Single-cell Phylogeny Reconstruction (SPhyR), a method for tumor phylogeny estimation from single-cell sequencing data. In light of frequent loss of SNVs due to CNAs in cancer, SPhyR employs the k-Dollo evolutionary model, where a mutation can only be gained once but lost k times. Underlying SPhyR is a novel combinatorial characterization of solutions as constrained integer matrix completions, based on a connection to the cladistic multi-state perfect phylogeny problem. SPhyR outperforms existing methods on simulated data and on a metastatic colorectal cancer. SPhyR is available on https://github.com/elkebir-group/SPhyR. Supplementary data are available at Bioinformatics online.