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.25
URN: urn:nbn:de:0030-drops-76470
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7647/
Go to the corresponding LIPIcs Volume Portal

Toivonen, Jarkko ; Taipale, Jussi ; Ukkonen, Esko

Seed-driven Learning of Position Probability Matrices from Large Sequence Sets

pdf-format:
LIPIcs-WABI-2017-25.pdf (0.6 MB)

Abstract

We formulate and analyze a novel seed-driven algorithm SeedHam for PPM learning. To learn a PPM of length l, the algorithm uses the most frequent l-mer of the training data as a seed, and then restricts the learning into a small Hamming neighbourhood of the seed. The SeedHam method is intended for PPM learning from large sequence sets (up to hundreds of Mbases) containing enriched motif instances. A robust variant of the method is introduced that decreases contamination from artefact instances of the motif and thereby allows using larger Hamming neighbourhoods. To solve the motif orientation problem in two-stranded DNA we introduce a novel seed finding rule, based on analysis of the palindromic structure of sequences. Test experiments are reported, that illustrate the relative strengths of different variants of our methods, and show that our algorithms are fast and give stable and accurate results.

Availability and implementation: A C++ implementation of the method is available from https://github.com/jttoivon/seedham/

Contact: jarkko.toivonen@cs.helsinki.fi

BibTeX - Entry

@InProceedings{toivonen_et_al:LIPIcs:2017:7647,
  author =	{Jarkko Toivonen and Jussi Taipale and Esko Ukkonen},
  title =	{{Seed-driven Learning of Position Probability Matrices from Large Sequence Sets}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{25:1--25: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/7647},
  URN =		{urn:nbn:de:0030-drops-76470},
  doi =		{10.4230/LIPIcs.WABI.2017.25},
  annote =	{Keywords: motif finding, transcription factor binding site, sequence analysis, Hamming distance, seed}
}

Keywords: motif finding, transcription factor binding site, sequence analysis, Hamming distance, seed
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