Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Sands Thesis.pdf (1.21 MB)

ETD Abstract Container

Abstract Header

Phylogenetic Inference Using a Discrete-Integer Linear Programming Model

Sands, William Alvah
http://rave.ohiolink.edu/etdc/view?acc_num=akron1492783280743802

Abstract Details

2017, Master of Science, University of Akron, Applied Mathematics.
Combinatorial methods have proved to be useful in generating relaxations of polytopes in various areas of mathematical programming. In this work, we propose a discrete-integer linear programming model for a recent version of the Phylogeny Estimation Problem (PEP), known as the Balanced Minimal Evolution Method (BME). We begin by examining an object known as the Balanced Minimal Evolution Polytope and several classes of geometric constraints that result in its relaxation. We use this information to develop the linear program and propose two Branch and Bound algorithms to solve the model. The second algorithm takes advantage of a heuristic known as a large neighborhood search. We provide experimental results for both algorithms, using perfect and noisy data, as well as suggestions for further improvement.
Stefan Forcey, Dr. (Advisor)
Malena Espanol, Dr. (Committee Member)
Patrick Wilber, Dr. (Committee Member)
77 p.
Applied Mathematics; Biology
Phylogenetics; Trees; Distance Methods; Balanced Minimal Evolution; Polytopes; Relaxation; Linear Programming; Discrete Constraints; Branch and Bound; Heuristic; Large Neighborhood Search

Recommended Citations

Citations

  • Sands, W. A. (2017). Phylogenetic Inference Using a Discrete-Integer Linear Programming Model [Master's thesis, University of Akron]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=akron1492783280743802

    APA Style (7th edition)

  • Sands, William. Phylogenetic Inference Using a Discrete-Integer Linear Programming Model. 2017. University of Akron, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=akron1492783280743802.

    MLA Style (8th edition)

  • Sands, William. "Phylogenetic Inference Using a Discrete-Integer Linear Programming Model." Master's thesis, University of Akron, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=akron1492783280743802

    Chicago Manual of Style (17th edition)

akron1492783280743802
204
© 2017, all rights reserved.
This open access ETD is published by University of Akron and OhioLINK.