Phylogenetic tree/network construction and comparison

Participants: Jannson Jesper, Wing-Kin Sung

Background

Phylogenetic tree is used to study the evaluation relationship among a set of taxa. It has been used in many different biological areas.

Objectives

In our project, we aim to develop method for constructing and comparing phylogenetic trees and networks. We have a few subprojects:

• Phylognetic network construction: In this project, we aim to construct phylogenetic networks from a set of triplets or a set of phylogenetic trees.
• Phylogenetic tree/network comparison: By applying different datasets and different techniques, we will create different phylogenetic trees for the same set of taxa. To understand the differences and the similarity of different phylogenetic trees, we can compare them. Our team has developed a number of methods to compute the MAST, the triplet distance of different phylogenetic trees/networks.
• Consensus tree construction: As stated above, we have many different phylogenetic trees for the same set of taxa. A consensus tree is a single phylogenetic tree that summarizes the branching structure in a given set of conflicting phylogenetic trees.

  The concept of a consensus tree was introduced by Adams in 1972, and the tree constructed by Adams is nowadays referred to as the Adams consensus tree. Afterwords, many different types of consensus trees have been proposed. They include the majority rule consensus tree, the loose consensus tree, the greedy consensus tree, the R* consensus tree, etc.

  Algorithms for building consensus tree is available in the literature. They are also implemented in different software packages like COMPONENT, EPoS, and PAUP*. However, many existing methods run in qraduatic time. In this project, we aim to improve the running time of those methods.

Software

• FACT: Fast Algorithms for Consensus Trees

Selected Publications

• Jesper Jansson, Ramesh Rajaby, Wing-Kin Sung. An Efficient Algorithm for the Rooted Triplet Distance Between Galled Trees. AlCoB, 115-126, 2017.

• Jesper Jansson, Andrzej Lingas, Ramesh Rajaby, Wing-Kin Sung. Determining the Consistency of Resolved Triplets and Fan Triplets. RECOMB, 82-98, 2017.

• Jesper Jansson, Wing-Kin Sung, Hoa Vu, Siu-Ming Yiu. Faster Algorithms for Computing the R* Consensus Tree. Algorithmica, 76(4): 1224-1244, 2016.

• Jesper Jansson, Chuanqi Shen, Wing-Kin Sung: Improved Algorithms for Constructing Consensus Trees. J. ACM, 63(3): 28:1-28:24, 2016.

• Jansson, J., Li, Z. and Wing-Kin Sung. On Finding the Adams Consensus Tree. 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, 487-499, March 2015.

• Jansson, J., Sung, W.-K., Vu, H. and Yiu, S. Faster Algorithms for Computing the R* Consensus Tree. ISAAC, 2014.

• Jansson, J., Shen, C. and Sung, W.-K. An Optimal Algorithm for Building the Majority Rule Consensus Tree. RECOMB, 88-99, 2013.

• Jansson, J., Shen, C. and Sung, W.-K. Improved Algorithms for Constructing Consensus Trees. SODA, 1800-1813, 2013.

• Jansson, J., Shen, C. and Sung, W.-K. Algorithms for the Majority Rule (+) Consensus Tree and the Frequency Difference Consensus Tree. WABI, 141-155, 2013.

• Jansson, J. and Sung, W.-K. Constructing the R* Consensus Tree of Two Trees in Subcubic Time. Algorithmica, Vol. 66(2), pp. 329-345, 2013.

• Cui, Y., Jansson, J. and Sung, W.-K. Polynomial-Time Algorithms for Building a Consensus MUL-Tree. J Comput Biol, Vol. 19(9), pp. 1073-1088, 2012.

• Cui, Y., Jansson, J. and Sung, W.-K. Algorithms for Building Consensus MUL-trees. ISAAC, 744-753, 2011.

• Jansson, J. and Sung, W.-K. Constructing the R* Consensus Tree of Two Trees in Subcubic Time. ESA (1), 573-584, 2010.