License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2017.21
URN: urn:nbn:de:0030-drops-76598
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7659/
Go to the corresponding LIPIcs Volume Portal

Quedenfeld, Jens ; Rahmann, Sven

Analysis of Min-Hashing for Variant Tolerant DNA Read Mapping

pdf-format:
LIPIcs-WABI-2017-21.pdf (0.5 MB)

Abstract

DNA read mapping has become a ubiquitous task in bioinformatics. New technologies provide ever longer DNA reads (several thousand basepairs), although at comparatively high error rates (up to 15%), and the reference genome is increasingly not considered as a simple string over ACGT anymore, but as a complex object containing known genetic variants in the population. Conventional indexes based on exact seed matches, in particular the suffix array based FM index, struggle with these changing conditions, so other methods are being considered, and one such alternative is locality sensitive hashing.

Here we examine the question whether including single nucleotide polymorphisms (SNPs) in a min-hashing index is beneficial. The answer depends on the population frequency of the SNP, and we analyze several models (from simple to complex) that provide precise answers to this question under various assumptions. Our results also provide sensitivity and specificity values for min-hashing based read mappers and may be used to understand dependencies between the parameters of such methods. We hope that this article will provide a theoretical foundation for a new generation of read mappers.

BibTeX - Entry

@InProceedings{quedenfeld_et_al:LIPIcs:2017:7659,
  author =	{Jens Quedenfeld and Sven Rahmann},
  title =	{{Analysis of Min-Hashing for Variant Tolerant DNA Read Mapping}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Russell Schwartz and Knut Reinert},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7659},
  URN =		{urn:nbn:de:0030-drops-76598},
  doi =		{10.4230/LIPIcs.WABI.2017.21},
  annote =	{Keywords: read mapping, min-Hashing, variant, SNP, analysis of algorithms}
}

Keywords: read mapping, min-Hashing, variant, SNP, analysis of algorithms
Collection: 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)
Issue Date: 2017
Date of publication: 11.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI