Robinson-Foulds Median Trees: A Clique-based Heuristic

Jucheol Moon
Thursday, September 29, 2016 - 3:40pm
2019 Morrill Hall
Event Type: 


Species trees are branching diagrams depicting the evolutionary relationships among a set of species, and species trees are inferred from gene trees that are describing the evolutionary history of genes. Unfortunately, for many genes the corresponding gene trees have discordant topologies when compared to the actual species tree, and to each other. Solving Robinson-Foulds median tree problems is a common approach to reconcile discordance in gene trees in order to infer a species tree. The Robinson-Foulds median tree problem seeks a median tree for a given collection of gene trees under the Robinson-Foulds distance. While this problem is NP-hard, it has been addressed by standard local search heuristics. This talk describes a fundamentally different heuristic that is based on a novel clique-based formulation of the Robinson-Foulds median tree problem.


Jucheol Moon is a Ph.D. student of Computer Science at ISU since 2012. He received his M.S. degree in Computer Science from South Dakota State University in 2012. His research interest is in algorithmic and theoretical properties of problems and machine learning in Computational Biology and Bioinformatics. He has published 2 journal papers and 7 conference papers in these areas.

Home page: