Multiple sequence recovery: theory and applications

In this dissertation, we seek to understand the feasibility of recovering multiple sequences from a set of observations containing information about the source sequences, referred to here as the multiple sequence recovery problem. As we will demonstrate, this problem plays an imperative role in areas such as DNA coding for data storage and computational biology. Since many algorithms for DNA assembly and error correction use k-mers, or substrings of length k, of input sequences, we first consider the task of reconstructing multiple source strings from the complete collection of their k-mers; specifically, under what conditions on k and string length n can m strings be uniquely reconstructed in the asymptotic regime. Our results nearly fully characterize the feasibility of this problem, and an intriguing discovery we make is that the feasible region overlaps with the “repeat-abundant region,” i.e., where k-mers occur multiple times within and between source strings with probability approaching 1. Next, we examine a coded scenario, where a set of M strings of length L are treated as a single codeword from a known codebook, and each string is corrupted by erasures and observed (i.e., drawn with replacement) a random number of times. We analyze both the single-draw and multi-draw versions of this channel model. In the single-draw version, the problem reduces to attempting to assemble the strings in the same order as the source codeword. However, the multi-draw version involves the challenge of determining the set of noisy reads corresponding to each of the input strings to attempt to eliminate erasures. We find a generalized expression for the capacity of both cases and prove that linear coding schemes achieve that capacity. The last part of this work tackles the problem of haplotype recovery, attempting to characterize the antibiotic resistome of a metagenomic sample. We begin by proving the statistical consistency of two different estimators for the set of haplotype sequences: the maximum likelihood estimator and a clustering method that minimizes the worst-case bit error across all haplotype clusters. Finally, we construct and demonstrate two practical methods for determining the resistome of real samples.

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

• Levick, Kel

Contributors dc:contributor

• Shomorony, Ilan
• Hajek, Bruce
• Milenkovic, Olgica
• Slizovskiy, Ilya
• Veeravalli, Venugopal

• information theory
• coding
• bioinformatics
• computational biology
• DNA storage

Statement dc:rights

• Copyright 2025 Kel Levick

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/132807