Oyekanmi, Adedoyin2023-11-172023-11-172022https://hdl.handle.net/10539/37026A dissertation submitted in fulfilment of the requirements for the degree of Master of Science to the Faculty of Science, University of the Witwatersrand, Johannesburg, 2022In 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.enSeeding heuristics methodSequence alignmentDissertation