Sequence alignment using the seeding heuristics method
Date
2022
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this dissertation, we studied Guillaume J. Filion’s paper on utilizing analytic combinatorics to calculate the probability that a read of size (s = k) has no seed (P(S)). First, we computed the weighted generating functions of all reads and reads that have no seed by constructing sequences of combinatorial objects using transfer graphs and transfer matrices as formulated by Filion. Then, we extended his logic to calculate the probability that a seed is present in a read (1 − P(S)) by singularity analysis, after obtaining the probability that a read has no seed. This involved extracting coefficients of weighted generating functions and solving complex polynomials which is the analytic combinatorics approach. Finally, we use recurrence approach (on Mathematica) to find more precise probabilities than what was provided by Filion for some practical examples.
Description
A dissertation submitted in fulfilment of the requirements for the degree of Master of Science to the Faculty of Science, University of the Witwatersrand, Johannesburg, 2022
Keywords
Seeding heuristics method, Sequence alignment