{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/132807"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/132807","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Multiple sequence recovery: theory and applications","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Levick, Kel"],"institution":"University of Illinois Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Shomorony, Ilan","Hajek, Bruce","Milenkovic, Olgica","Slizovskiy, Ilya","Veeravalli, Venugopal"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-12","date_published":"2025-12","updated_at":"2026-07-22T22:25:07Z","subjects":["information theory","coding","bioinformatics","computational biology","DNA storage"],"languages":["en"],"rights":["Copyright 2025 Kel Levick"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/132807","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Shomorony, Ilan","Hajek, Bruce","Milenkovic, Olgica","Slizovskiy, Ilya","Veeravalli, Venugopal"]},{"key":"dc:creator","label":"Author","values":["Levick, Kel"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-12","2025-12-09"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["information theory","coding","bioinformatics","computational biology","DNA storage"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Kel Levick"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/132807"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-12-01","The student, Kel Levick, accepted the attached license on 2025-12-09 at 07:42.","The student, Kel Levick, submitted this Dissertation for approval on 2025-12-09 at 08:10.","This Dissertation was approved for publication on 2025-12-09 at 10:23.","DSpace SAF Submission Ingestion Package generated from Vireo submission #23109 on 2026-02-19 at 20:10:08"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Multiple sequence recovery: theory and applications"]}]}],"canonical_facts":{"dc:contributor":["Shomorony, Ilan","Hajek, Bruce","Milenkovic, Olgica","Slizovskiy, Ilya","Veeravalli, Venugopal"],"dc:creator":["Levick, Kel"],"dc:date":["2025-12","2025-12-09"],"dc:description":["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.","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-12-01","The student, Kel Levick, accepted the attached license on 2025-12-09 at 07:42.","The student, Kel Levick, submitted this Dissertation for approval on 2025-12-09 at 08:10.","This Dissertation was approved for publication on 2025-12-09 at 10:23.","DSpace SAF Submission Ingestion Package generated from Vireo submission #23109 on 2026-02-19 at 20:10:08"],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/132807"],"dc:language":["en"],"dc:rights":["Copyright 2025 Kel Levick"],"dc:subject":["information theory","coding","bioinformatics","computational biology","DNA storage"],"dc:title":["Multiple sequence recovery: theory and applications"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:07Z"}