Large-scale methods for multiple sequence alignment and phylogeny estimation

Smirnov, Vladimir A

Permalink

https://hdl.handle.net/2142/113015 Copy

Description

Title

Large-scale methods for multiple sequence alignment and phylogeny estimation

Author(s)

Smirnov, Vladimir A

Issue Date

2021-07-12

Director of Research (if dissertation) or Advisor (if thesis)

Warnow, Tandy

Doctoral Committee Chair(s)

Warnow, Tandy

Committee Member(s)

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

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2021-08

Type of Resource

Thesis

Permalink

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

Copyright and License Information

Copyright 2021 Vladimir Smirnov

Owning Collections