Efficient and scalable algorithms for phylogenomics and overlapping communities

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Liu, Baqiao

Contributors dc:contributor

• Warnow, Tandy
• Rauchwerger, Lawrence
• El-Kebir, Mohammed
• Tong, Hanghang
• Bader, David A

• Phylogenomics
• Species Trees
• Phylogenetics
• Incomplete Lineage Sorting
• Multispecies Coalescent
• Multiple Sequence Alignment
• Chapel
• Computational Biology
• Sequence Length Heterogeneity

Statement dc:rights

• Copyright 2024 Baqiao Liu

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

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