Algorithms for Reconstructing Biological History from Genomic Data

In this thesis, we study several problems related to computational biology surrounding a central theme: inferring temporally-spaced events using noisy measurements. The first half studies two theoretical problems for explaining the history of human populations at different scales. First, we present sample complexity results for learning population structures given pairwise coalescence data. The second involves pedigree reconstruction, in which we prove that there is a sample-efficient algorithm for reconstructing a “family tree” given a population-wide collection of genomic information. The second half of the thesis concerns models for the microbiome and practical algorithms that emphasize scalability and interpretability. We present work on strain tracking, in which one is asked to reconstruct a time-series profile of bacterial strain ratios from shotgun-sequenced reads. We state an algorithm designed to scale on large data, discuss some real-world considerations that makes the problem particularly challenging, and present empirical results. Last but not least, we present collaborative work on dynamical systems modeling of the microbiome, in which we discuss how one can learn a large, yet interpretable, Lotka-Volterra model from time-series measurements of the microbiome.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Mathematics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Kim, Younhun

Advisor dc:contributor.advisor

• Berger, Bonnie

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/150079

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/150079