Abstract

Recently large databases containing profile Hidden Markov Models (pHMMs) emerged. These pHMMs may represent the sequences of antibiotic resistance genes, or allelic variations amongst highly conserved housekeeping genes used for strain typing, etc. The typical application of such a database includes the alignment of contigs to pHMM hoping that the sequence of gene of interest is located within the single contig. Such a condition is often violated for metagenomes preventing the effective use of such databases. We present PathRacer—a novel standalone tool that aligns profile HMM directly to the assembly graph (performing the codon translation on fly for amino acid pHMMs). The tool provides the set of most probable paths traversed by a HMM through the whole assembly graph, regardless whether the sequence of interested is encoded on the single contig or scattered across the set of edges, therefore significantly improving the recovery of sequences of interest even from fragmented metagenome assemblies.

Original languageEnglish
Title of host publication6th International Conference on Algorithms for Computational Biology
EditorsMiguel A. Vega-Rodríguez, Ian Holmes, Carlos Martín-Vide
PublisherSpringer Nature
Pages80-94
Number of pages15
ISBN (Print)9783030181734
DOIs
Publication statusPublished - 25 May 2019
Event6th International Conference on Algorithms for Computational Biology, AlCoB 2019 - Berkeley
Duration: 28 May 201930 May 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11488 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Conference on Algorithms for Computational Biology, AlCoB 2019
CountryUnited States
CityBerkeley
Period28/05/1930/05/19

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'PathRacer: Racing Profile HMM Paths on Assembly Graph'. Together they form a unique fingerprint.

  • Cite this

    Shlemov, A., & Korobeynikov, A. (2019). PathRacer: Racing Profile HMM Paths on Assembly Graph. In M. A. Vega-Rodríguez, I. Holmes, & C. Martín-Vide (Eds.), 6th International Conference on Algorithms for Computational Biology (pp. 80-94). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11488 LNBI). Springer Nature. https://doi.org/10.1007/978-3-030-18174-1_6