This event has ended. View the official site or create your own event → Check it out
This event has ended. Create your own
View analytic
Thursday, August 3 • 12:00 - 12:20
Analytic combinatorics for bioinformatics: applications to seeding and genome assembly

Sign up or log in to save this to your schedule and see who's attending!

One of the main challenges of modern bioinformatics is to meet the ever-growing demand for sequencing-based analyses. Most of the sequenced reads are aligned to a reference genome, explaining why large efforts have been invested into developing efficient alignment algorithms. The algorithms rely on seed-based heuristics, where short regions of near-identity are used to rapidly zoom in on candidate targets. This makes the algorithms faster, but it also makes them inexact, creating a risk of missing the best hit. Surprisingly, the chance that sequencing reads contain seeds of different lengths is not part of the common knowledge in bioinformatics. The answer depends on the sequencing technology so the problem has so far remained without a general solution. Meanwhile, the rapidly evolving field of “analytic combinatorics” has initiated a radical shift towards answering such problems. The principle is to use symbolic manipulations to construct a mathematical function encapsulating the solution to the problem, instead of using standard approximations. Using analytic combinatorics, I provide a practical solution to estimate the probabilities of occurrences of seeds for arbitrary error models. With this knowledge, I propose a new way to calibrate seeding heuristics, giving more accurate mapping qualities and allowing better rationalization of the mapping process. The approach also works for all including empirical error models and for inexact seeds with up to one error. The analytic combinatorics approach also has applications to the assembly problem, where it provides very accurate estimates for the expected contig number and contig size, even in regimes where the classical estimators fail. Overall, this work shows how to use the novel and fruitful approach of analytic combinatorics to solve some modern problems in bioinformatics.


Thursday August 3, 2017 12:00 - 12:20
Graduate School of Management Building, room 309 Volkhovskiy Pereulok, 3, St. Petersburg, Russia

Attendees (1)