Salt Lake City, Utah
June 23, 2018
June 23, 2018
July 27, 2018
We develop case study materials for innovative biological application of computational methods in Industrial Engineering; Convex Recoloring (CR) Problem on a Phylogenetic Tree.
The convex recoloring (CR) problem is to recolor the nodes of a colored graph at minimum number of color changes such that each color induces a connected subgraph, where the colored graph is a phylogenetic tree with leaf nodes assigned to pieces of protein sequences. If the minimum number is too large, the species represented in colors need to merge into one species. In the history of bioinformatics, linear programming has not been used while it is used in Industrial Engineering to solve many problems raised in almost every industry.
We adjust to the convex recoloring problem the column generation framework developed by Johnson, Mehrotra and Nemhauser in 1993. A column generation framework saves a lot of space complexity and can be developed in Excel Worksheet. For the convex recoloring problem on a phylogenetic tree, the subproblem to generate columns can be solved by Excel Solver as the size of the subproblem is very small.
The initial Excel Worksheet is designed by the authors to check in toy model if the column generation framework works well for the CR problem on a phylogenetic tree. The research appears in a decent proceedings in Industrial Engineering. The Worksheet is being refined by students taking an undergraduate optimization course as course project in Fall 2017. To increase the scale of the problem instances, they use Open Solver another add-in to Micro Soft Excel which is endorsed by Computational Infrastructure for Operations Research (COIN-OR.) The Worksheet will be used as course material in undergraduate optimization courses and computational methods courses in biomedical engineering.
Erdem, E., & Shim, S. (2018, June), Board 101 : A Steepest Edge Rule for a Column Generation Approach to the Convex Recoloring Problem Paper presented at 2018 ASEE Annual Conference & Exposition , Salt Lake City, Utah. https://peer.asee.org/29857
ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2018 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015