2026-07-23T05:05:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6080 2024-03-06T10:37:33Z ddc:004 open_access

Efficient Index for Weighted Sequences Barton, Carl Kociumaka, Tomasz Pissis, Solon P. Radoszewski, Jakub weighted sequence position weight matrix indexing weighted suffix tree The problem of finding factors of a text string which are identical or similar to a given pattern string is a central problem in computer science. A generalised version of this problem consists in implementing an index over the text to support efficient on-line pattern queries. We study this problem in the case where the text is weighted: for every position of the text and every letter of the alphabet a probability of occurrence of this letter at this position is given. Sequences of this type, also called position weight matrices, are commonly used to represent imprecise or uncertain data. A weighted sequence may represent many different strings, each with probability of occurrence equal to the product of probabilities of its letters at subsequent positions. Given a probability threshold 1/z, we say that a pattern string P matches a weighted text at position i if the product of probabilities of the letters of P at positions i,...,i+|P|-1 in the text is at least 1/z. In this article, we present an O(nz)-time construction of an O(nz)-sized index that can answer pattern matching queries in a weighted text in optimal time improving upon the state of the art by a factor of z log z. Other applications of this data structure include an O(nz)-time construction of the weighted prefix table and an O(nz)-time computation of all covers of a weighted sequence, which improve upon the state of the art by the same factor. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Carl Barton and Tomasz Kociumaka and Solon P. Pissis and Jakub Radoszewski 2016 Is Part Of LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2016.4 urn:nbn:de:0030-drops-60807 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.4 eng https://creativecommons.org/licenses/by/3.0/legalcode