Fundamental limits and algorithms for sequence reconstruction, alignment, and analysis

This dissertation studies several problems concerning the reconstruction, alignment, and analysis of sequences. The results obtained are all motivated by or applicable to problems involving biological sequences, e.g. DNA, RNA, and proteins. These applications include privacy-preserving DNA sequencing, the reconstruction of proteins from tandem mass spectrometry data, DNA data storage, phylogeny inference, protein structure and function inference, and the clustering of cells into cell-types based on gene expression. The specific problems studied concern trace reconstruction, multiple sequence alignment, density-based clustering, flow graph decomposition, and information-theoretic privacy. The contributions in this dissertation are theoretical and algorithmic in nature, but applications to real datasets are included in some cases.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Mazooji, Kayvon Amir

Contributors dc:contributor

• Shomorony, Ilan
• Milenkovic, Olgica
• Raginsky, Maxim
• Zhao, Zhizhen

• information theory
• statistics
• algorithms
• computational biology

Statement dc:rights

• Copyright 2025 Kayvon Amir Mazooji

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129454

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129454