LLLei Liu

Lei Liu

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Lei Liu has a total of 2 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Testing the Agreement of Trees with Internal Labels

    by David Fernández-Baca, Lei Liu

    Background: A semi-labeled tree is a tree where all leaves as well as, possibly, some internal nodes are labeledwith taxa. Semi-labeled trees encompass ordinary phylogenetic trees and taxonomies. Suppose we are given a collection P = {T1, T2, . . . , Tk} of semi-labeled trees, called input trees, over partially overlapping sets of taxa. The agreement problem asks whether there exists a tree T , called an agreement tree, whose taxon set is the union of the taxon sets of the input trees such that the restriction of T to the taxon set of Ti is isomorphic to i, for each i ε 1, 2, . . . , k . The agreement problems is a special case of the supertree problem, the problem of synthesizing a collection of phylogenetic trees with partially overlapping taxon sets into a single supertree that represents the information in the input trees. An obstacle to building large phylogenetic supertrees is the limited amount of taxonomic overlap among the phylogenetic studies from which the input trees are obtained. Incorporating taxonomies into supertree analyses can alleviate this issue. Results: We give a O(nk(i∈[k]di + log2(nk))) algorithm for the agreement problem, where n is the total number of distinct taxa in P, k is the number of trees in P, and di is the maximum number of children of a node in Ti. Our computational experience with the algorithm suggests that its performance in practice is much better than its worst-case bound indicates.


  • Open Access

    Testing the Agreement of Trees with Internal Labels

    by David Fernández-Baca, Lei Liu

    The input to the agreement problem is a collection $P = \{T_1, T_2, \dots , T_k\}$ of phylogenetic trees, called input trees, over partially overlapping sets of taxa. The question is whether there exists a tree $T$, called an agreement tree, whose taxon set is the union of the taxon sets of the input trees, such that for each $i \in \{1, 2, \dots , k\}$, the restriction of $T$ to the taxon set of $T_i$ is isomorphic to $T_i$. We give a $O(n k (\sum_{i \in [k]} d_i + \log^2(nk)))$ algorithm for a generalization of the agreement problem in which the input trees may have internal labels, where $n$ is the total number of distinct taxa in $P$, $k$ is the number of trees in $P$, and $d_i$ is the maximum number of children of a node in $T_i$.

  • Open Access

    Tree Compatibility, Incomplete Directed Perfect Phylogeny, and Dynamic Graph Connectivity: An Experimental Study

    by David Fernández-Baca, Lei Liu

    We study two problems in computational phylogenetics. The first is tree compatibility. The input is a collection P of phylogenetic trees over different partially-overlapping sets of species. The goal is to find a single phylogenetic tree that displays all the evolutionary relationships implied by P . The second problem is incomplete directed perfect phylogeny (IDPP). The input is a data matrix describing a collection of species by a set of characters, where some of the information is missing. The question is whether there exists a way to fill in the missing information so that the resulting matrix can be explained by a phylogenetic tree satisfying certain conditions. We explain the connection between tree compatibility and IDPP and show that a recent tree compatibility algorithm is effectively a generalization of an earlier IDPP algorithm. Both algorithms rely heavily on maintaining the connected components of a graph under a sequence of edge and vertex deletions, for which they use the dynamic connectivity data structure of Holm et al., known as HDT. We present a computational study of algorithms for tree compatibility and IDPP. We show experimentally that substituting HDT by a much simpler data structure—essentially, a single-level version of HDT—improves the performance of both of these algorithm in practice. We give partial empirical and theoretical justifications for this observation.