@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 {38545, title = {Transforming men into mice (polynomial algorithm for genomic distance problem)}, year = {1995}, month = {1995}, publisher = {IEEE Computer Society}, type = {http://doi.ieeecomputersociety.org/10.1109/SFCS.1995.492588}, address = {Los Alamitos, CA, USA}, abstract = {Many people believe that transformations of humans into mice happen only in fairy tales. However, despite some differences in appearance and habits, men and mice are genetically very similar. In the pioneering paper, J.H. Nadeau and B.A. Taylor (1984) estimated that surprisingly few genomic rearrangements (178/spl plusmn/39) happened since the divergence of human and mouse 80 million years ago. However, their analysis is nonconstructive and no rearrangement scenario for human-mouse evolution has been suggested yet. The problem is complicated by the fact that rearrangements in multi chromosomal genomes include inversions, translocations, fusions and fissions of chromosomes, a rather complex set of operations. As a result, at first glance, a polynomial algorithm for the genomic distance problem with all these operations looks almost as improbable as the transformation of a (real) man into a (real) mouse. We prove a duality theorem which expresses the genomic distance in terms of easily computable parameters reflecting different combinatorial properties of sets of strings. This theorem leads to a polynomial time algorithm for computing most parsimonious rearrangement scenarios. Based on this result and the latest comparative physical mapping data we have constructed a scenario of human-mouse evolution with 131 reversals/translocaitons/fusions/fissions. A combination of the genome rearrangement algorithm with the recently proposed experimental technique called ZOO FISH suggests a new constructive approach to the 100 year old problem of reconstructing mammalian evolution.}, keywords = {biology computing, combinatorial properties, comparative physical mapping data, computable parameters, duality (mathematics), duality theorem, evolution (biological), Genetics, genome rearrangement algorithm, genomic distance problem, genomic rearrangements, human-mouse evolution, mammalian evolution, multi chromosomal genomes, parsimonious rearrangement scenarios, pattern matching, polynomial algorithm, polynomial time algorithm, set theory, sorting, string matching, strings, zoo fish}, author = {Sridhar Hannenhalli and Pevzner, P. A.} }