{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/125530"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/125530","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Efficient and scalable algorithms for phylogenomics and overlapping communities","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","abstract_has_math":false,"creators":["Liu, Baqiao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Warnow, Tandy","Rauchwerger, Lawrence","El-Kebir, Mohammed","Tong, Hanghang","Bader, David A"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-06-24","date_published":"2024-06-24","updated_at":"2026-07-22T22:25:02Z","subjects":["Phylogenomics","Species Trees","Phylogenetics","Incomplete Lineage Sorting","Multispecies Coalescent","Multiple Sequence Alignment","Chapel","Computational Biology","Sequence Length Heterogeneity"],"languages":["en","eng"],"rights":["Copyright 2024 Baqiao Liu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/125530","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Warnow, Tandy","Rauchwerger, Lawrence","El-Kebir, Mohammed","Tong, Hanghang","Bader, David A"]},{"key":"dc:creator","label":"Author","values":["Liu, Baqiao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-06-24","2024-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"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 at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Phylogenomics","Species Trees","Phylogenetics","Incomplete Lineage Sorting","Multispecies Coalescent","Multiple Sequence Alignment","Chapel","Computational Biology","Sequence Length Heterogeneity"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2024 Baqiao Liu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/125530"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","The student, Baqiao Liu, accepted the attached license on 2024-06-21 at 13:48.","The student, Baqiao Liu, submitted this Dissertation for approval on 2024-06-21 at 15:43.","This Dissertation was approved for publication on 2024-06-24 at 10:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20858 on 2025-02-04 at 21:03:47","In computational biology, the reconstruction of evolutionary histories is a fundamental problem. Phylogenomics, the reconstruction of evolutionary history using genomics data, like many other sub-areas of computational biology, has benefited tremendously from computational techniques and has a rich tradition of both computational theory and practice. This thesis contributes to this field by developing scalable and accurate computational algorithms in two sub-areas of phylogenomics -- species tree estimation, and multiple sequence alignment. Moreover, we generalize our discrete algorithm research into overlapping community detection in large-scale networks, with a slightly different focus on high performance computing. Our work in phylogenomics centers first on species tree estimation, a challenging task due to evolutionary complexities like incomplete lineage sorting and gene tree reconstruction error. We introduce Weighted ASTRID, an extension of the ASTRID method; we notably enhance species tree estimations by incorporating gene tree uncertainty inspired by recent works. This approach significantly boosts both accuracy and robustness in the face of gene tree reconstruction error, and we designed a more efficient implementation of ASTRID. Additionally, we present NJst-J and FASTRAL-J, methods leveraging prior species tree knowledge for refined inference. We venture briefly into multiple sequence alignment with WITCH-NG, an optimized version of the prior method WITCH both algorithmically and implementation-wise for adding new sequences into existing alignments. These contributions collectively offer not only theoretical advancements but also efficiently implemented practical tools for the phylogenomics community. In parallel, the dissertation extends into overlapping community detection in large-scale networks, acting as a generalization of our study of discrete algorithms in trees to real world networks. Using the Chapel programming language, we propose novel methodologies within the Arachne graph framework, designing a distributed version of the HDBSCAN clustering method specialized for graph clustering. This body of work emphasizes a balance between theoretical accuracy and practical efficiency. We not only contribute to the theoretical efficiency of the algorithms, but all our algorithms are also efficiently implemented, leveraging modern programming languages, hardware capabilities, and software engineering practices."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Efficient and scalable algorithms for phylogenomics and overlapping communities"]}]}],"canonical_facts":{"dc:contributor":["Warnow, Tandy","Rauchwerger, Lawrence","El-Kebir, Mohammed","Tong, Hanghang","Bader, David A"],"dc:creator":["Liu, Baqiao"],"dc:date":["2024-06-24","2024-08"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms","The student, Baqiao Liu, accepted the attached license on 2024-06-21 at 13:48.","The student, Baqiao Liu, submitted this Dissertation for approval on 2024-06-21 at 15:43.","This Dissertation was approved for publication on 2024-06-24 at 10:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20858 on 2025-02-04 at 21:03:47","In computational biology, the reconstruction of evolutionary histories is a fundamental problem. Phylogenomics, the reconstruction of evolutionary history using genomics data, like many other sub-areas of computational biology, has benefited tremendously from computational techniques and has a rich tradition of both computational theory and practice. This thesis contributes to this field by developing scalable and accurate computational algorithms in two sub-areas of phylogenomics -- species tree estimation, and multiple sequence alignment. Moreover, we generalize our discrete algorithm research into overlapping community detection in large-scale networks, with a slightly different focus on high performance computing. Our work in phylogenomics centers first on species tree estimation, a challenging task due to evolutionary complexities like incomplete lineage sorting and gene tree reconstruction error. We introduce Weighted ASTRID, an extension of the ASTRID method; we notably enhance species tree estimations by incorporating gene tree uncertainty inspired by recent works. This approach significantly boosts both accuracy and robustness in the face of gene tree reconstruction error, and we designed a more efficient implementation of ASTRID. Additionally, we present NJst-J and FASTRAL-J, methods leveraging prior species tree knowledge for refined inference. We venture briefly into multiple sequence alignment with WITCH-NG, an optimized version of the prior method WITCH both algorithmically and implementation-wise for adding new sequences into existing alignments. These contributions collectively offer not only theoretical advancements but also efficiently implemented practical tools for the phylogenomics community. In parallel, the dissertation extends into overlapping community detection in large-scale networks, acting as a generalization of our study of discrete algorithms in trees to real world networks. Using the Chapel programming language, we propose novel methodologies within the Arachne graph framework, designing a distributed version of the HDBSCAN clustering method specialized for graph clustering. This body of work emphasizes a balance between theoretical accuracy and practical efficiency. We not only contribute to the theoretical efficiency of the algorithms, but all our algorithms are also efficiently implemented, leveraging modern programming languages, hardware capabilities, and software engineering practices."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/125530"],"dc:language":["en","eng"],"dc:rights":["Copyright 2024 Baqiao Liu"],"dc:subject":["Phylogenomics","Species Trees","Phylogenetics","Incomplete Lineage Sorting","Multispecies Coalescent","Multiple Sequence Alignment","Chapel","Computational Biology","Sequence Length Heterogeneity"],"dc:title":["Efficient and scalable algorithms for phylogenomics and overlapping communities"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:02Z"}