@article {49616, title = {The Theory and Practice of Genome Sequence Assembly}, journal = {Annu Rev Genomics Hum GenetAnnu Rev Genomics Hum Genet}, volume = {16}, year = {2015}, note = {Simpson, Jared T
Pop, Mihai
eng
2015/05/06 06:00
Annu Rev Genomics Hum Genet. 2015 Aug 24;16:153-72. doi: 10.1146/annurev-genom-090314-050032. Epub 2015 Apr 22.}, month = {Aug 24}, pages = {153-72}, abstract = {The current genomic revolution was made possible by joint advances in genome sequencing technologies and computational approaches for analyzing sequence data. The close interaction between biologists and computational scientists is perhaps most apparent in the development of approaches for sequencing entire genomes, a feat that would not be possible without sophisticated computational tools called genome assemblers (short for genome sequence assemblers). Here, we survey the key developments in algorithms for assembling genome sequences since the development of the first DNA sequencing methods more than 35 years ago.}, keywords = {algorithm, Bioinformatics, genome sequencing, sequence assembly, shotgun sequencing}, isbn = {1545-293X (Electronic)
1527-8204 (Linking)}, author = {Simpson, J. T. and Pop, M.} } @proceedings {38374, title = {MetaPhyler: Taxonomic profiling for metagenomic sequences}, year = {2010}, month = {2010}, publisher = {IEEE}, type = {10.1109/BIBM.2010.5706544}, abstract = {A major goal of metagenomics is to characterize the microbial diversity 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 16S rRNA gene between even closely related organisms, and due to PCR artifacts. The taxonomic composition can also be determined from whole-metagenome sequencing data by matching individual sequences against a database of reference genes. One major limitation of prior 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 profiler MetaPhyler, which uses 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 obtained by applying MetaPhyler to a real metagenomic dataset.}, keywords = {Bioinformatics, CARMA comparison, Databases, Genomics, Linear regression, marker genes, matching length, Megan comparison, metagenomic sequences, metagenomics, MetaPhyler, microbial diversity, microorganisms, molecular biophysics, molecular configurations, Pattern classification, pattern matching, phylogenetic classification, Phylogeny, PhymmBL comparison, reference gene database, Sensitivity, sequence matching, taxonomic classifier, taxonomic level, taxonomic profiling, whole metagenome sequencing data}, isbn = {978-1-4244-8306-8}, author = {Liu, Bo and Gibbons, T. and Ghodsi, M. and M. Pop} } @proceedings {38343, title = {Inexact Local Alignment Search over Suffix Arrays}, year = {2009}, month = {2009}, publisher = {IEEE}, type = {10.1109/BIBM.2009.25}, abstract = {We describe an algorithm for finding approximate seeds for DNA homology searches. In contrast to previous algorithms that use exact or spaced seeds, our approximate seeds may contain insertions and deletions. We present a generalized heuristic for finding such seeds efficiently and prove that the heuristic does not affect sensitivity. We show how to adapt this algorithm to work over the memory efficient suffix array with provably minimal overhead in running time. We demonstrate the effectiveness of our algorithm on two tasks: whole genome alignment of bacteria and alignment of the DNA sequences of 177 genes that are orthologous in human and mouse. We show our algorithm achieves better sensitivity and uses less memory than other commonly used local alignment tools.}, keywords = {bacteria, Bioinformatics, biology computing, Computational Biology, Costs, DNA, DNA homology searches, DNA sequences, Educational institutions, generalized heuristic, genes, Genetics, genome alignment, Genomics, human, inexact local alignment search, inexact seeds, local alignment, local alignment tools, memory efficient suffix array, microorganisms, molecular biophysics, mouse, Organisms, Sensitivity and Specificity, sequences, suffix array, USA Councils}, isbn = {978-0-7695-3885-3}, author = {Ghodsi, M. and M. Pop} } @article {38379, title = {Microbial oceanography in a sea of opportunity}, journal = {NatureNature}, volume = {459}, year = {2009}, type = {10.1038/nature08056}, abstract = {Plankton use solar energy to drive the nutrient cycles that make the planet habitable for larger organisms. We can now explore the diversity and functions of plankton using genomics, revealing the gene repertoires associated with survival in the oceans. Such studies will help us to appreciate the sensitivity of ocean systems and of the ocean{\textquoteright}s response to climate change, improving the predictive power of climate models.}, keywords = {Astronomy, astrophysics, Biochemistry, Bioinformatics, Biology, biotechnology, cancer, cell cycle, cell signalling, climate change, Computational Biology, development, developmental biology, DNA, drug discovery, earth science, ecology, environmental science, Evolution, evolutionary biology, functional genomics, Genetics, Genomics, geophysics, immunology, interdisciplinary science, life, marine biology, materials science, medical research, medicine, metabolomics, molecular biology, molecular interactions, nanotechnology, Nature, neurobiology, neuroscience, palaeobiology, pharmacology, Physics, proteomics, quantum physics, RNA, Science, science news, science policy, signal transduction, structural biology, systems biology, transcriptomics}, isbn = {0028-0836}, author = {Bowler, Chris and Karl, David M. and Rita R. Colwell} } @proceedings {38555, title = {Uncovering Genomic Reassortments among Influenza Strains by Enumerating Maximal Bicliques}, year = {2008}, month = {2008}, publisher = {IEEE}, type = {10.1109/BIBM.2008.78}, abstract = {The evolutionary histories of viral genomes have received significant recent attention due to their importance in understanding virulence and the corresponding ramifications to public health. We present a novel framework to detect reassortment events in influenza based on the comparison of two distributions of phylogenetic trees, rather than a pair of, possibly unreliable, consensus trees. We show how to detect all high-probability inconsistencies between two distributions of trees by enumerating maximal bicliques within a defined incompatibility graph. In the process, we give the first quadratic delay algorithm for enumerating maximal bicliques within general bipartite graphs. We demonstrate the utility of our approach by applying it to several sets of influenza genomes (both human- and avian-hosted) and successfully identify all known reassortment events and a few novel candidate reassortments. In addition, on simulated datasets, our approach correctly finds implanted reassortments and rarely detects reassortments where none were introduced.}, keywords = {avian hosted influenza genome, Bioinformatics, Capacitive sensors, Delay, diseases, Event detection, general bipartite graphs, genomic reassortments, Genomics, graph theory, high probability inconsistencies, History, human hosted influenza genome, incompatibility graph, Influenza, influenza strain, maximal biclique, maximal biclique enumeration, microorganisms, phylogenetic trees, Phylogeny, Public healthcare, quadratic delay algorithm, reassortment, reassortment event detection, Tree graphs, viral genome evolutionary history, virulence}, isbn = {978-0-7695-3452-7}, author = {Nagarajan, N. and Kingsford, Carl} } @proceedings {38218, title = {Dynamic querying for pattern identification in microarray and genomic data}, volume = {3}, year = {2003}, month = {2003}, publisher = {IEEE}, type = {10.1109/ICME.2003.1221346}, abstract = {Data sets involving linear ordered sequences are a recurring theme in bioinformatics. Dynamic query tools that support exploration of these data sets can be useful for identifying patterns of interest. This paper describes the use of one such tool - timesearcher - to interactively explore linear sequence data sets taken from two bioinformatics problems. Microarray time course data sets involve expression levels for large numbers of genes over multiple time points. Timesearcher can be used to interactively search these data sets for genes with expression profiles of interest. The occurrence frequencies of short sequences of DNA in aligned exons can be used to identify sequences that play a role in the pre-mRNA splicing. Timesearcher can be used to search these data sets for candidate splicing signals.}, keywords = {Bioinformatics, data sets, Displays, dynamic querying, expression profiles, Frequency, Gene expression, genes, Genetics, genomic data, Genomics, linear ordered sequences, macromolecules, medical signal processing, Mice, Microarray, pattern identification, pattern recognition, premRNA splicing, Query processing, sequences, Signal processing, splicing, TimeSearcher}, isbn = {0-7803-7965-9}, author = {Hochheiser, H. and Baehrecke, E. H. and Stephen M. Mount and Shneiderman, Ben} }