@inbook{3794a8d8292c421684cf5f0a59c6852d,
title = "On-line pattern matching on uncertain sequences and applications",
abstract = "We study the fundamental problem of pattern matching in the case where the string data is weighted: for every position of the string and every letter of the alphabet a probability of occurrence for this letter at this position is given. Sequences of this type are commonly used to represent uncertain data. They are of particular interest in computational molecular biology as they can represent different kind of ambiguities in DNA sequences: distributions of SNPs in genomes populations; position frequency matrices of DNA binding profiles; or even sequencingrelated uncertainties. A weighted string may thus represent many different strings, each with probability of occurrence equal to the product of probabilities of its letters at subsequent positions. In this article, we present new average-case results on pattern matching on weighted strings and show how they are applied effectively in several biological contexts. A free open-source implementation of our algorithms is made available.",
author = "Carl Barton and Chang Liu and Solon Pissis",
year = "2016",
doi = "10.1007/978-3-319-48749-6_40",
language = "English",
isbn = "9783319487489",
volume = "10043 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer‐Verlag Berlin Heidelberg",
pages = "547--562",
editor = "Chan, {T-H. Hubert} and Minming Li and Lusheng Wang",
booktitle = "Combinatorial Optimization and Applications: 10th International Conference, COCOA 2016, Hong Kong, China, December 16--18, 2016, Proceedings",
note = "10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016 ; Conference date: 16-12-2016 Through 18-12-2016",
}