Computer Science Research Works

Permanent URI for this collectionhttp://hdl.handle.net/1903/1593

Browse

Author: search.filters.author.Pop, MihaiStart date: 1973

Search Results

Now showing 1 - 10 of 19
  • Thumbnail Image
    Item
    Genome assembly forensics: finding the elusive mis-assembly
    (Springer Nature, 2008-03-14) Phillippy, Adam M; Schatz, Michael C; Pop, Mihai
    We present the first collection of tools aimed at automated genome assembly validation. This work formalizes several mechanisms for detecting mis-assemblies, and describes their implementation in our automated validation pipeline, called amosvalidate. We demonstrate the application of our pipeline in both bacterial and eukaryotic genome assemblies, and highlight several assembly errors in both draft and finished genomes. The software described is compatible with common assembly formats and is released, open-source, at http://amos.sourceforge.net .
  • Thumbnail Image
    Item
    Ultrafast and memory-efficient alignment of short DNA sequences to the human genome
    (Springer Nature, 2009-03-04) Langmead, Ben; Trapnell, Cole; Pop, Mihai; Salzberg, Steven L
    Bowtie is an ultrafast, memory-efficient alignment program for aligning short DNA sequence reads to large genomes. For the human genome, Burrows-Wheeler indexing allows Bowtie to align more than 25 million reads per CPU hour with a memory footprint of approximately 1.3 gigabytes. Bowtie extends previous Burrows-Wheeler techniques with a novel quality-aware backtracking algorithm that permits mismatches. Multiple processor cores can be used simultaneously to achieve even greater alignment speeds. Bowtie is open source http://bowtie.cbcb.umd.edu .
  • Thumbnail Image
    Item
    MetaPath: identifying differentially abundant metabolic pathways in metagenomic datasets
    (Springer Nature, 2011-04-28) Liu, Bo; Pop, Mihai
    Enabled by rapid advances in sequencing technology, metagenomic studies aim to characterize entire communities of microbes bypassing the need for culturing individual bacterial members. One major goal of metagenomic studies is to identify specific functional adaptations of microbial communities to their habitats. The functional profile and the abundances for a sample can be estimated by mapping metagenomic sequences to the global metabolic network consisting of thousands of molecular reactions. Here we describe a powerful analytical method (MetaPath) that can identify differentially abundant pathways in metagenomic datasets, relying on a combination of metagenomic sequence data and prior metabolic pathway knowledge. First, we introduce a scoring function for an arbitrary subnetwork and find the max-weight subnetwork in the global network by a greedy search algorithm. Then we compute two p values (p abund and p struct ) using nonparametric approaches to answer two different statistical questions: (1) is this subnetwork differentically abundant? (2) What is the probability of finding such good subnetworks by chance given the data and network structure? Finally, significant metabolic subnetworks are discovered based on these two p values. In order to validate our methods, we have designed a simulated metabolic pathways dataset and show that MetaPath outperforms other commonly used approaches. We also demonstrate the power of our methods in analyzing two publicly available metagenomic datasets, and show that the subnetworks identified by MetaPath provide valuable insights into the biological activities of the microbiome. We have introduced a statistical method for finding significant metabolic subnetworks from metagenomic datasets. Compared with previous methods, results from MetaPath are more robust against noise in the data, and have significantly higher sensitivity and specificity (when tested on simulated datasets). When applied to two publicly available metagenomic datasets, the output of MetaPath is consistent with previous observations and also provides several new insights into the metabolic activity of the gut microbiome. The software is freely available at http://metapath.cbcb.umd.edu .
  • Thumbnail Image
    Item
    Accurate and fast estimation of taxonomic profiles from metagenomic shotgun sequences
    (Springer Nature, 2011-07-27) Liu, Bo; Gibbons, Theodore; Ghodsi, Mohammad; Treangen, Todd; Pop, Mihai
    A major goal of metagenomics is to characterize the microbial composition of an environment. The most popular approach relies on 16S rRNA sequencing, however this approach can generate biased estimates due to differences in the copy number of the gene between even closely related organisms, and due to PCR artifacts. The taxonomic composition can also be determined from metagenomic shotgun sequencing data by matching individual reads against a database of reference sequences. One major limitation of prior computational methods used for this purpose is the use of a universal classification threshold for all genes at all taxonomic levels. We propose that better classification results can be obtained by tuning the taxonomic classifier to each matching length, reference gene, and taxonomic level. We present a novel taxonomic classifier MetaPhyler (http://metaphyler.cbcb.umd.edu), which uses phylogenetic marker genes as a taxonomic reference. Results on simulated datasets demonstrate that MetaPhyler outperforms other tools commonly used in this context (CARMA, Megan and PhymmBL). We also present interesting results by analyzing a real metagenomic dataset. We have introduced a novel taxonomic classification method for analyzing the microbial diversity from whole-metagenome shotgun sequences. Compared with previous approaches, MetaPhyler is much more accurate in estimating the phylogenetic composition. In addition, we have shown that MetaPhyler can be used to guide the discovery of novel organisms from metagenomic samples.
  • Thumbnail Image
    Item
    Exploiting sparseness in de novo genome assembly
    (Springer Nature, 2012-04-19) Ye, Chengxi; Sam Ma, Zhanshan; Cannon, Charles H; Pop, Mihai; Yu, Douglas W
    The very large memory requirements for the construction of assembly graphs for de novo genome assembly limit current algorithms to super-computing environments. In this paper, we demonstrate that constructing a sparse assembly graph which stores only a small fraction of the observed k- mers as nodes and the links between these nodes allows the de novo assembly of even moderately-sized genomes (~500 M) on a typical laptop computer. We implement this sparse graph concept in a proof-of-principle software package, SparseAssembler, utilizing a new sparse k- mer graph structure evolved from the de Bruijn graph. We test our SparseAssembler with both simulated and real data, achieving ~90% memory savings and retaining high assembly accuracy, without sacrificing speed in comparison to existing de novo assemblers.
  • Thumbnail Image
    Item
    MetAMOS: a modular and open source metagenomic assembly and analysis pipeline
    (Springer Nature, 2013-01-15) Treangen, Todd J; Koren, Sergey; Sommer, Daniel D; Liu, Bo; Astrovskaya, Irina; Ondov, Brian; Darling, Aaron E; Phillippy, Adam M; Pop, Mihai
    We describe MetAMOS, an open source and modular metagenomic assembly and analysis pipeline. MetAMOS represents an important step towards fully automated metagenomic analysis, starting with next-generation sequencing reads and producing genomic scaffolds, open-reading frames and taxonomic or functional annotations. MetAMOS can aid in reducing assembly errors, commonly encountered when assembling metagenomic samples, and improves taxonomic assignment accuracy while also reducing computational cost. MetAMOS can be downloaded from: https://github.com/treangen/MetAMOS .
  • Thumbnail Image
    Item
    Diarrhea in young children from low-income countries leads to large-scale alterations in intestinal microbiota composition
    (Springer Nature, 2014-06-27) Pop, Mihai; Walker, Alan W; Paulson, Joseph; Lindsay, Brianna; Antonio, Martin; Hossain, M Anowar; Oundo, Joseph; Tamboura, Boubou; Mai, Volker; Astrovskaya, Irina; Bravo, Hector Corrada; Rance, Richard; Stares, Mark; Levine, Myron M; Panchalingam, Sandra; Kotloff, Karen; Ikumapayi, Usman N; Ebruke, Chinelo; Adeyemi, Mitchell; Ahmed, Dilruba; Ahmed, Firoz; Alam, Meer Taifur; Amin, Ruhul; Siddiqui, Sabbir; Ochieng, John B; Ouma, Emmanuel; Juma, Jane; Mailu, Euince; Omore, Richard; Morris, J Glenn; Breiman, Robert F; Saha, Debasish; Parkhill, Julian; Nataro, James P; Stine, O Colin
    Diarrheal diseases continue to contribute significantly to morbidity and mortality in infants and young children in developing countries. There is an urgent need to better understand the contributions of novel, potentially uncultured, diarrheal pathogens to severe diarrheal disease, as well as distortions in normal gut microbiota composition that might facilitate severe disease. We use high throughput 16S rRNA gene sequencing to compare fecal microbiota composition in children under five years of age who have been diagnosed with moderate to severe diarrhea (MSD) with the microbiota from diarrhea-free controls. Our study includes 992 children from four low-income countries in West and East Africa, and Southeast Asia. Known pathogens, as well as bacteria currently not considered as important diarrhea-causing pathogens, are positively associated with MSD, and these include Escherichia/Shigella, and Granulicatella species, and Streptococcus mitis/pneumoniae groups. In both cases and controls, there tend to be distinct negative correlations between facultative anaerobic lineages and obligate anaerobic lineages. Overall genus-level microbiota composition exhibit a shift in controls from low to high levels of Prevotella and in MSD cases from high to low levels of Escherichia/Shigella in younger versus older children; however, there was significant variation among many genera by both site and age. Our findings expand the current understanding of microbiota-associated diarrhea pathogenicity in young children from developing countries. Our findings are necessarily based on correlative analyses and must be further validated through epidemiological and molecular techniques.
  • Thumbnail Image
    Item
    Construction of a dairy microbial genome catalog opens new perspectives for the metagenomic analysis of dairy fermented products
    (Springer Nature, 2014-12-13) Almeida, Mathieu; Hébert, Agnès; Abraham, Anne-Laure; Rasmussen, Simon; Monnet, Christophe; Pons, Nicolas; Delbès, Céline; Loux, Valentin; Batto, Jean-Michel; Leonard, Pierre; Kennedy, Sean; Ehrlich, Stanislas Dusko; Pop, Mihai; Montel, Marie-Christine; Irlinger, Françoise; Renault, Pierre
    Microbial communities of traditional cheeses are complex and insufficiently characterized. The origin, safety and functional role in cheese making of these microbial communities are still not well understood. Metagenomic analysis of these communities by high throughput shotgun sequencing is a promising approach to characterize their genomic and functional profiles. Such analyses, however, critically depend on the availability of appropriate reference genome databases against which the sequencing reads can be aligned. We built a reference genome catalog suitable for short read metagenomic analysis using a low-cost sequencing strategy. We selected 142 bacteria isolated from dairy products belonging to 137 different species and 67 genera, and succeeded to reconstruct the draft genome of 117 of them at a standard or high quality level, including isolates from the genera Kluyvera, Luteococcus and Marinilactibacillus, still missing from public database. To demonstrate the potential of this catalog, we analysed the microbial composition of the surface of two smear cheeses and one blue-veined cheese, and showed that a significant part of the microbiota of these traditional cheeses was composed of microorganisms newly sequenced in our study. Our study provides data, which combined with publicly available genome references, represents the most expansive catalog to date of cheese-associated bacteria. Using this extended dairy catalog, we revealed the presence in traditional cheese of dominant microorganisms not deliberately inoculated, mainly Gram-negative genera such as Pseudoalteromonas haloplanktis or Psychrobacter immobilis, that may contribute to the characteristics of cheese produced through traditional methods.
  • Thumbnail Image
    Item
    Use and mis-use of supplementary material in science publications
    (Springer Nature, 2015-11-03) Pop, Mihai; Salzberg, Steven L.
    Supplementary material is a ubiquitous feature of scientific articles, particularly in journals that limit the length of the articles. While the judicious use of supplementary material can improve the readability of scientific articles, its excessive use threatens the scientific review process and by extension the integrity of the scientific literature. In many cases supplementary material today is so extensive that it is reviewed superficially or not at all. Furthermore, citations buried within supplementary files rob other scientists of recognition of their contribution to the scientific record. These issues are exacerbated by the lack of guidance on the use of supplementary information from the journals to authors and reviewers. We propose that the removal of artificial length restrictions plus the use of interactive features made possible by modern electronic media can help to alleviate these problems. Many journals, in fact, have already removed article length limitations (as is the case for BMC Bioinformatics and other BioMed Central journals). We hope that the issues raised in our article will encourage publishers and scientists to work together towards a better use of supplementary information in scientific publishing.
  • Thumbnail Image
    Item
    Scaffolding of long read assemblies using long range contact information
    (Springer Nature, 2017-07-12) Ghurye, Jay; Pop, Mihai; Koren, Sergey; Bickhart, Derek; Chin, Chen-Shan
    Long read technologies have revolutionized de novo genome assembly by generating contigs orders of magnitude longer than that of short read assemblies. Although assembly contiguity has increased, it usually does not reconstruct a full chromosome or an arm of the chromosome, resulting in an unfinished chromosome level assembly. To increase the contiguity of the assembly to the chromosome level, different strategies are used which exploit long range contact information between chromosomes in the genome. We develop a scalable and computationally efficient scaffolding method that can boost the assembly contiguity to a large extent using genome-wide chromatin interaction data such as Hi-C. We demonstrate an algorithm that uses Hi-C data for longer-range scaffolding of de novo long read genome assemblies. We tested our methods on the human and goat genome assemblies. We compare our scaffolds with the scaffolds generated by LACHESIS based on various metrics. Our new algorithm SALSA produces more accurate scaffolds compared to the existing state of the art method LACHESIS.