BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Taoyang Wu

Taoyang Wu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Populations and Evolutionmath.COData Structures and Algorithmsmath.PRmath.MGMolecular NetworksQuantitative Methods

Catalog footprint

What is connected

16works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2022arXiv

Planar Rooted Phylogenetic Networks

A rooted phylogenetic network is a directed acyclic graph with a single root, whose sinks correspond to a set of species. As such networks are useful for representing the evolution of species that have undergone reticulate evolution, there has been great interest in developing the theory behind and algorithms for constructing them. However, unlike evolutionary trees, these networks can be highly non-planar, which can make them difficult to visualise and interpret. Here we investigate properties of planar rooted phylogenetic networks and algorithms for deciding whether or not rooted networks have certain special planarity properties. In particular, we introduce three natural subclasses of planar rooted phylogenetic networks and show that they form a hierarchy. In addition, for the well-known level-k networks, we show that level-1, -2, -3 networks are always outer, terminal, and upward planar, respectively, and that level-4 networks are not necessarily planar. Finally, we show that a regular network is terminal planar if and only if it is pyramidal. Our results make use of the highly developed field of planar digraphs, and we believe that the link between phylogenetic networks and planar graphs should prove useful in future for developing new approaches to both construct and visualise phylogenetic networks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Posets and spaces of $k$-noncrossing RNA Structures

RNA molecules are single-stranded analogues of DNA that can fold into various structures which influence their biological function within the cell. RNA structures can be modelled combinatorially in terms of a certain type of graph called an RNA diagram. In this paper we introduce a new poset of RNA diagrams $\mathcal{B}^r_{f,k}$, $r\ge 0$, $k \ge 1$ and $f \ge 3$, which we call the Penner-Waterman poset, and, using results from the theory of multitriangulations, we show that this is a pure poset of rank $k(2f-2k+1)+r-f-1$, whose geometric realization is the join of a simplicial sphere of dimension $k(f-2k)-1$ and an $\left((f+1)(k-1)-1\right)$-simplex in case $r=0$. As a corollary for the special case $k=1$, we obtain a result due to Penner and Waterman concerning the topology of the space of RNA secondary structures. These results could eventually lead to new ways to investigate landscapes of RNA $k$-noncrossing structures.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On asymptotic joint distributions of cherries and pitchforks for random phylogenetic trees

Tree shape statistics provide valuable quantitative insights into evolutionary mechanisms underpinning phylogenetic trees, a commonly used graph representation of evolution systems ranging from viruses to species. By developing limit theorems for a version of extended Pólya urn models in which negative entries are permitted for their replacement matrices, we present strong laws of large numbers and central limit theorems for asymptotic joint distributions of two subtree counting statistics, the number of cherries and that of pitchforks, for random phylogenetic trees generated by two widely used null tree models: the proportional to distinguishable arrangements (PDA) and the Yule-Harding-Kingman (YHK) models. Our results indicate that the limiting behaviour of these two statistics, when appropriately scaled, are independent of the initial trees used in the tree generating process.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On cherry and pitchfork distributions of random rooted and unrooted phylogenetic trees

Tree shape statistics are important for investigating evolutionary mechanisms mediating phylogenetic trees. As a step towards bridging shape statistics between rooted and unrooted trees, we present a comparison study on two subtree statistics known as numbers of cherries and pitchforks for the proportional to distinguishable arrangements (PDA) and the Yule-Harding-Kingman (YHK) models. Based on recursive formulas on the joint distribution of the number of cherries and that of pitchforks, it is shown that cherry distributions are log-concave for both rooted and unrooted trees under these two models. Furthermore, the mean number of cherries and that of pitchforks for unrooted trees converge respectively to those for rooted trees under the YHK model while there exists a limiting gap of 1/4 for the PDA model. Finally, the total variation distances between the cherry distributions of rooted and those of unrooted trees converge for both models. Our results indicate that caution is required for conducting statistical analysis for tree shapes involving both rooted and unrooted trees.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Reduction rules for the maximum parsimony distance on phylogenetic trees

In phylogenetics, distances are often used to measure the incongruence between a pair of phylogenetic trees that are reconstructed by different methods or using different regions of genome. Motivated by the maximum parsimony principle in tree inference, we recently introduced the maximum parsimony (MP) distance, which enjoys various attractive properties due to its connection with several other well-known tree distances, such as TBR and SPR. Here we show that computing the MP distance between two trees, a NP-hard problem in general, is fixed parameter tractable in terms of the TBR distance between the tree pair. Our approach is based on two reduction rules--the chain reduction and the subtree reduction--that are widely used in computing TBR and SPR distances. More precisely, we show that reducing chains to length 4 (but not shorter) preserves the MP distance. In addition, we describe a generalization of the subtree reduction which allows the pendant subtrees to be rooted in different places, and show that this still preserves the MP distance. On a slightly different note we also show that Monadic Second Order Logic (MSOL), posited over an auxiliary graph structure known as the display graph (obtained by merging the two trees at their leaves), can be used to obtain an alternative proof that computation of MP distance is fixed parameter tractable in terms of TBR-distance. We conclude with an extended discussion in which we focus on similarities and differences between MP distance and TBR distance and present a number of open problems. One particularly intriguing question, emerging from the MSOL formulation, is whether two trees with bounded MP distance induce display graphs of bounded treewidth.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Transforming phylogenetic networks: Moving beyond tree space

Phylogenetic networks are a generalization of phylogenetic trees that are used to represent reticulate evolution. Unrooted phylogenetic networks form a special class of such networks, which naturally generalize unrooted phylogenetic trees. In this paper we define two operations on unrooted phylogenetic networks, one of which is a generalization of the well-known nearest-neighbor interchange (NNI) operation on phylogenetic trees. We show that any unrooted phylogenetic network can be transformed into any other such network using only these operations. This generalizes the well-known fact that any phylogenetic tree can be transformed into any other such tree using only NNI operations. It also allows us to define a generalization of tree space and to define some new metrics on unrooted phylogenetic networks. To prove our main results, we employ some fascinating new connections between phylogenetic networks and cubic graphs that we have recently discovered. Our results should be useful in developing new strategies to search for optimal phylogenetic networks, a topic that has recently generated some interest in the literature, as well as for providing new ways to compare networks.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Folding and unfolding phylogenetic trees and networks

Phylogenetic networks are rooted, labelled directed acyclic graphs which are commonly used to represent reticulate evolution. There is a close relationship between phylogenetic networks and multi-labelled trees (MUL-trees). Indeed, any phylogenetic network $N$ can be 'unfolded' to obtain a MUL-tree $U(N)$ and, conversely, a MUL-tree $T$ can in certain circumstances be 'folded' to obtain a phylogenetic network $F(T)$ that exhibits $T$. In this paper, we study properties of the operations $U$ and $F$ in more detail. In particular, we introduce the class of stable networks, phylogenetic networks $N$ for which $F(U(N))$ is isomorphic to $N$, characterise such networks, and show that that they are related to the well-known class of tree-sibling networks. We also explore how the concept of displaying a tree in a network $N$ can be related to displaying the tree in the MUL-tree $U(N)$. To do this, we develop a phylogenetic analogue of graph fibrations. This allows us to view $U(N)$ as the analogue of the universal cover of a digraph, and to establish a close connection between displaying trees in $U(N)$ and reconciling phylogenetic trees with networks.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On joint subtree distributions under two evolutionary models

In population and evolutionary biology, hypotheses about micro-evolutionary and macro-evolutionary processes are commonly tested by comparing the shape indices of empirical evolutionary trees with those predicted by neutral models. A key ingredient in this approach is the ability to compute and quantify distributions of various tree shape indices under random models of interest. As a step to meet this challenge, in this paper we investigate the joint distribution of cherries and pitchforks (that is, subtrees with two and three leaves) under two widely used null models: the Yule-Harding-Kingman (YHK) model and the proportional to distinguishable arrangements (PDA) model. Based on two novel recursive formulae, we propose a dynamic approach to numerically compute the exact joint distribution (and hence the marginal distributions) for trees of any size. We also obtained insights into the statistical properties of trees generated under these two models, including a constant correlation between the cherry and the pitchfork distributions under the YHK model, the log-concavity and unimodality of cherry distributions under both models. In particular, we show the existence of a unique change point for cherry distribution between the two models, that is, there exists a critical value $τ_n$ for each $n\geq 4$ such that the probability that a random tree with $n$ leaves generated under the YHK model contains $k$ cherries is lower than that under the PDA model if $1<k< τ_n$, and higher if $τ_n<k\le n/2$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal realisations of two-dimensional, totally-decomposable metrics

A realisation of a metric $d$ on a finite set $X$ is a weighted graph $(G,w)$ whose vertex set contains $X$ such that the shortest-path distance between elements of $X$ considered as vertices in $G$ is equal to $d$. Such a realisation $(G,w)$ is called optimal if the sum of its edge weights is minimal over all such realisations. Optimal realisations always exist, although it is NP-hard to compute them in general, and they have applications in areas such as phylogenetics, electrical networks and internet tomography. In [Adv. in Math. 53, 1984, 321-402] A.~Dress showed that the optimal realisations of a metric $d$ are closely related to a certain polytopal complex that can be canonically associated to $d$ called its tight-span. Moreover, he conjectured that the (weighted) graph consisting of the zero- and one-dimensional faces of the tight-span of $d$ must always contain an optimal realisation as a homeomorphic subgraph. In this paper, we prove that this conjecture does indeed hold for a certain class of metrics, namely the class of totally"=decomposable metrics whose tight-span has dimension two. As a corollary, it follows that the minimum Manhattan network problem is a special case of finding optimal realisations of two-dimensional totally-decomposable metrics.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Clades and clans: a comparison study of two evolutionary models

The Yule-Harding-Kingman (YHK) model and the proportional to distinguishable arrangements (PDA) model are two binary tree generating models that are widely used in evolutionary biology. Understanding the distributions of clade sizes under these two models provides valuable insights into macro-evolutionary processes, and is important in hypothesis testing and Bayesian analyses in phylogenetics. Here we show that these distributions are log-convex, which implies that very large clades or very small clades are more likely to occur under these two models. Moreover, we prove that there exists a critical value $κ(n)$ for each $n\geqslant 4$ such that for a given clade with size $k$, the probability that this clade is contained in a random tree with $n$ leaves generated under the YHK model is higher than that under the PDA model if $1<k<κ(n)$, and lower if $κ(n)<k<n$. Finally, we extend our results to binary unrooted trees, and obtain similar results for the distributions of clan sizes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets

Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set $\mathcal{T}$ of binary binets or trinets over a set $X$ of taxa, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an $O(3^{|X|} poly(|X|))$ time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Representing Partitions on Trees

In evolutionary biology, biologists often face the problem of constructing a phylogenetic tree on a set $X$ of species from a multiset $Π$ of partitions corresponding to various attributes of these species. One approach that is used to solve this problem is to try instead to associate a tree (or even a network) to the multiset $Σ_Π$ consisting of all those bipartitions $\{A,X-A\}$ with $A$ a part of some partition in $Π$. The rational behind this approach is that a phylogenetic tree with leaf set $X$ can be uniquely represented by the set of bipartitions of $X$ induced by its edges. Motivated by these considerations, given a multiset $Σ$ of bipartitions corresponding to a phylogenetic tree on $X$, in this paper we introduce and study the set $P(Σ)$ consisting of those multisets of partitions $Π$ of $X$ with $Σ_Π=Σ$. More specifically, we characterize when $P(Σ)$ is non-empty, and also identify some partitions in $P(Σ)$ that are of maximum and minimum size. We also show that it is NP-complete to decide when $P(Σ)$ is non-empty in case $Σ$ is an arbitrary multiset of bipartitions of $X$. Ultimately, we hope that by gaining a better understanding of the mapping that takes an arbitrary partition system $Π$ to the multiset $Σ_Π$, we will obtain new insights into the use of median networks and, more generally, split-networks to visualize sets of partitions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Patchworks and Hierarchies

Motivated by questions in biological classification, we discuss some elementary combinatorial and computational properties of certain set systems that generalize hierarchies, namely, 'patchworks', 'weak patchworks', 'ample patchworks' and 'saturated patchworks' and also outline how these concepts relate to an apparently new 'duality theory' for cluster systems that is based on the fundamental concept of 'compatibility' of clusters.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the neighbourhoods of trees

Tree rearrangement operations typically induce a metric on the space of phylogenetic trees. One important property of these metrics is the size of the neighbourhood, that is, the number of trees exactly one operation from a given tree. We present an expression for the size of the TBR (tree bisection and reconnection) neighbourhood, thus answering a question first posed in [Annals of Combinatorics, 5, 2001 1-15].

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Reconciliation of Gene and Species Trees With Polytomies

Motivation: Millions of genes in the modern species belong to only thousands of `gene families'. A gene family includes instances of the same gene in different species (orthologs) and duplicate genes in the same species (paralogs). Genes are gained and lost during evolution. With advances in sequencing technology, researchers are able to investigate the important roles of gene duplications and losses in adaptive evolution. Because of gene complex evolution, ortholog identification is a basic but difficult task in comparative genomics. A key method for the task is to use an explicit model of the evolutionary history of the genes being studied, called the gene (family) tree. It compares the gene tree with the evolutionary history of the species in which the genes reside, called the species tree, using the procedure known as tree reconciliation. Reconciling binary gene and specific trees is simple. However, both gene and species trees may be non-binary in practice and thus tree reconciliation presents challenging problems. Here, non-binary gene and species tree reconciliation is studied in a binary refinement model. Results: The problem of reconciling arbitrary gene and species trees is proved NP-hard even for the duplication cost. We then present the first efficient method for reconciling a non-binary gene tree and a non-binary species tree. It attempts to find binary refinements of the given gene and species trees that minimize reconciliation cost. Our algorithms have been implemented into a software to support quick automated analysis of large data sets. Availability: The program, together with the source code, is available at its online server http://phylotoo.appspot.com.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Reconstruction of Network Evolutionary History from Extant Network Topology and Duplication History

Genome-wide protein-protein interaction (PPI) data are readily available thanks to recent breakthroughs in biotechnology. However, PPI networks of extant organisms are only snapshots of the network evolution. How to infer the whole evolution history becomes a challenging problem in computational biology. In this paper, we present a likelihood-based approach to inferring network evolution history from the topology of PPI networks and the duplication relationship among the paralogs. Simulations show that our approach outperforms the existing ones in terms of the accuracy of reconstruction. Moreover, the growth parameters of several real PPI networks estimated by our method are more consistent with the ones predicted in literature.

0 citations0 reviewsNo code linkedOpen access