Dear All

Algorithms for Maximum Agreement Forests: Recent Progresses

Start: 08/04/2014 1:00 pm
End: 08/04/2014 2:00 pm

Departmental Colloquium
Dr. Jianer Chen
Department of Computer Science and Engineering
Texas A&M University

The Maximum Agreement Forest Problem (MAF) has been proposed to facilitate the comparison of phylogenetic trees in the research of evolutionary biology, which corresponds to the Tree-Bisection-and-Reconnection (TBR) distance for unrooted trees and the Subtree-Prune-and-Regraft (SPR) distance for rooted trees. The problem is NP-hard and APX-hard. Approximation algorithms and parameterized algorithms for the problem have been extensively studied in the literature, mainly on two bifurcating (i.e., binary) trees. In this talk, we introduce new algorithmic techniques and study algorithms for the MAF problem on multifurcating (i.e., general) trees and on multiple (i.e., two or more) trees. For the MAF problem on multifurcating trees, we present an O(3^k n)-time parameterized algorithm, resolving an open problem in the literature, and the first constant-ratio approximation algorithm. For the MAF problem on multiple trees, we present parameterized algorithms and approximation algorithms for both rooted trees and unrooted trees. The performance and complexity of our algorithms either match or improve the best known results for the MAF problem on two trees.
About the Speaker: Jianer Chen received his PhD degrees in Computer Science from New York University, and his PhD degrees in Mathematics from Columbia University. He is a Professor in Computer Science at Texas A&M University, USA, and also holds ChangJiang Professorship and National 1000-Plan Professorship at Central South University, P.R. China. He is currently serving in the editorial board of Journal of Computer and System Sciences, IEEE Transactions on Computers, and Science in China: Information Sciences. His research interests include algorithms and computational optimization, computer graphics, bioinformatics, and computer networks. He has published extensively in these areas.

Aderhold Learning Center
C 31
--------

Thanks!
Yanqing