{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/110757"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/110757","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Information theoretic limits of metagenomic binning","abstract":"The goal of metagenomics is to study the composition of microbial communities, typically using high-throughput shotgun sequencing. In the metagenomic binning problem, we observe random substrings (called contigs) from a mixture of genomes and want to cluster them according to their genome of origin. Based on the empirical observation that genomes of different bacterial species can be distinguished based on their tetranucleotide frequencies, we model this task as the problem of clustering N sequences generated by M distinct Markov processes, where M ≪ N. Utilizing the large-deviation principle for Markov processes, we establish the information-theoretic limit for perfect binning. Specifically, we show that the length of the contigs must scale with the inverse of the Chernoff Information between the two most similar species. Our result also implies that contigs should be binned using the conditional relative entropy as a measure of distance, as opposed to the Euclidean distance often used in practice.","abstract_html":"The goal of metagenomics is to study the composition of microbial communities, typically using high-throughput shotgun sequencing. In the metagenomic binning problem, we observe random substrings (called contigs) from a mixture of genomes and want to cluster them according to their genome of origin. Based on the empirical observation that genomes of different bacterial species can be distinguished based on their tetranucleotide frequencies, we model this task as the problem of clustering N sequences generated by M distinct Markov processes, where M ≪ N. Utilizing the large-deviation principle for Markov processes, we establish the information-theoretic limit for perfect binning. Specifically, we show that the length of the contigs must scale with the inverse of the Chernoff Information between the two most similar species. Our result also implies that contigs should be binned using the conditional relative entropy as a measure of distance, as opposed to the Euclidean distance often used in practice.","abstract_has_math":false,"creators":["Greenberg, Grant"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Shomorony, Ilan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-09-17T02:34:51Z","date_published":"2021-09-17T02:34:51Z","updated_at":"2026-07-22T22:24:52Z","subjects":["Metagenomics","Information Theory","Large Deviation Theory","Computational Biology","Bioinformatics","Genomics"],"languages":["en"],"rights":["Copyright 2021 Grant Greenberg"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/110757","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Shomorony, Ilan"]},{"key":"dc:creator","label":"Author","values":["Greenberg, Grant"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-09-17T02:34:51Z","2023-09-17T02:34:57Z","2021-04-30","2021-05"]},{"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":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Metagenomics","Information Theory","Large Deviation Theory","Computational Biology","Bioinformatics","Genomics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Grant Greenberg"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/110757"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The goal of metagenomics is to study the composition of microbial communities, typically using high-throughput shotgun sequencing. In the metagenomic binning problem, we observe random substrings (called contigs) from a mixture of genomes and want to cluster them according to their genome of origin. Based on the empirical observation that genomes of different bacterial species can be distinguished based on their tetranucleotide frequencies, we model this task as the problem of clustering N sequences generated by M distinct Markov processes, where M ≪ N. Utilizing the large-deviation principle for Markov processes, we establish the information-theoretic limit for perfect binning. Specifically, we show that the length of the contigs must scale with the inverse of the Chernoff Information between the two most similar species. Our result also implies that contigs should be binned using the conditional relative entropy as a measure of distance, as opposed to the Euclidean distance often used in practice.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2023-05-01","The student, Grant Greenberg, accepted the attached license on 2021-04-30 at 09:06.","The student, Grant Greenberg, submitted this Thesis for approval on 2021-04-30 at 09:16.","This Thesis was approved for publication on 2021-04-30 at 09:32.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16620 on 2021-09-16 at 17:06:54","Made available in DSpace on 2021-09-17T02:34:51Z (GMT). No. of bitstreams: 3 GREENBERG-THESIS-2021.pdf: 633746 bytes, checksum: a612ae29970005be421046f59248518a (MD5) thesis.zip: 6622324 bytes, checksum: b921f217f9dc9f2a444f1570727fd8de (MD5) LICENSE.txt: 4212 bytes, checksum: 42b900533609cd690b1aae9f8f13b18f (MD5) Previous issue date: 2021-04-30","Embargo set by: Seth Robbins for item 118600 Lift date: 2023-09-17T02:34:57Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Information theoretic limits of metagenomic binning"]}]}],"canonical_facts":{"dc:contributor":["Shomorony, Ilan"],"dc:creator":["Greenberg, Grant"],"dc:date":["2021-09-17T02:34:51Z","2023-09-17T02:34:57Z","2021-04-30","2021-05"],"dc:description":["The goal of metagenomics is to study the composition of microbial communities, typically using high-throughput shotgun sequencing. In the metagenomic binning problem, we observe random substrings (called contigs) from a mixture of genomes and want to cluster them according to their genome of origin. Based on the empirical observation that genomes of different bacterial species can be distinguished based on their tetranucleotide frequencies, we model this task as the problem of clustering N sequences generated by M distinct Markov processes, where M ≪ N. Utilizing the large-deviation principle for Markov processes, we establish the information-theoretic limit for perfect binning. Specifically, we show that the length of the contigs must scale with the inverse of the Chernoff Information between the two most similar species. Our result also implies that contigs should be binned using the conditional relative entropy as a measure of distance, as opposed to the Euclidean distance often used in practice.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2023-05-01","The student, Grant Greenberg, accepted the attached license on 2021-04-30 at 09:06.","The student, Grant Greenberg, submitted this Thesis for approval on 2021-04-30 at 09:16.","This Thesis was approved for publication on 2021-04-30 at 09:32.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16620 on 2021-09-16 at 17:06:54","Made available in DSpace on 2021-09-17T02:34:51Z (GMT). No. of bitstreams: 3 GREENBERG-THESIS-2021.pdf: 633746 bytes, checksum: a612ae29970005be421046f59248518a (MD5) thesis.zip: 6622324 bytes, checksum: b921f217f9dc9f2a444f1570727fd8de (MD5) LICENSE.txt: 4212 bytes, checksum: 42b900533609cd690b1aae9f8f13b18f (MD5) Previous issue date: 2021-04-30","Embargo set by: Seth Robbins for item 118600 Lift date: 2023-09-17T02:34:57Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/110757"],"dc:language":["en"],"dc:rights":["Copyright 2021 Grant Greenberg"],"dc:subject":["Metagenomics","Information Theory","Large Deviation Theory","Computational Biology","Bioinformatics","Genomics"],"dc:title":["Information theoretic limits of metagenomic binning"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:52Z"}