Analytic combinatorics for computing seeding probabilities

DOI10.3390/A11010003MaRDI QIDQ2633234zbMATH OpenOpenAlexFDO

Authors Guillaume J. Filion

Publication date 8 May 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a11010003

zbMATH Keywords

analytic combinatoricsbioinformaticsgenerating functionsseeding sequence alignment

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Algorithms on strings (68W32) General biology and biomathematics (92B05)

Review text

Summary: Seeding heuristics are the most widely used strategies to speed up sequence alignment in bioinformatics. Such strategies are most successful if they are calibrated, so that the speed-versus-accuracy trade-off can be properly tuned. In the widely used case of read mapping, it has been so far impossible to predict the success rate of competing seeding strategies for lack of a theoretical framework. Here, we present an approach to estimate such quantities based on the theory of analytic combinatorics. The strategy is to specify a combinatorial construction of reads where the seeding heuristic fails, translate this specification into a generating function using formal rules, and finally extract the probabilities of interest from the singularities of the generating function. The generating function can also be used to set up a simple recurrence to compute the probabilities with greater precision. We use this approach to construct simple estimators of the success rate of the seeding heuristic under different types of sequencing errors, and we show that the estimates are accurate in practical situations. More generally, this work shows novel strategies based on analytic combinatorics to compute probabilities of interest in bioinformatics.

Recommendations

• On the complexity of the spaced seeds
• On spaced seeds for similarity search
• New Algorithms for the Spaced Seeds
• Sensitivity analysis and efficient method for identifying optimal spaced seeds
• Design and analysis of periodic multiple seeds

Cites work

• A word counting graph
• Analytic combinatorics
• Analytic combinatorics in several variables.
• Asymptotic Methods in Enumeration
• Biological Sequence Analysis
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Counting regular expressions in degenerated sequences through lazy Markov chain embedding
• Distribution Theory of Runs: A Markov Chain Approach
• Handbook of Enumerative Combinatorics
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes.
• Multiple pattern matching: a Markov chain approach
• Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata
• Singularity Analysis of Generating Functions
• Une théorie combinatoire des séries formelles

Describes a project that uses

Uses Software

• fsaLib
• R
• countmotif
• BWA

This page was built for publication: Analytic combinatorics for computing seeding probabilities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2633234)