Large-scale methods for multiple sequence alignment and phylogeny estimation

Bioinformatic analyses generally involve passing genetic sequence data through a pipeline of transformations. These prominently include multiple sequence alignment (MSA) and phylogeny estimation, which are both core challenges in computational biology. Their established mathematical formulations are usually difficult NP-hard problems that are attacked with careful and laborious heuristics. Consequently, the most accurate methods tend to be the most computationally expensive with increasing dataset size, and this limits the analysis to datasets of only modest volume. Larger datasets are becoming increasingly available and require qualitatively different approaches. In this thesis, we consider divide-and-conquer frameworks that employ slow-but-accurate base methods to efficiently solve the problem piecewise. The continued development of accurate and efficient large-scale methods will, it is hoped, facilitate more effective bioinformatic analysis of larger and larger datasets.

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

2022

Author dc:creator

• Smirnov, Vladimir A

Contributors dc:contributor

• Warnow, Tandy
• Peng, Jian
• Forsyth, David
• Treangen, Todd
• Pop, Mihai

• bioinformatics
• computational biology
• genetic sequences
• multiple sequence alignment
• phylogeny
• big data

Statement dc:rights

• Copyright 2021 Vladimir Smirnov

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/113015

OAI identifier oai:identifier

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