Search

Self-Other Reorganization (SOR) is a theory of how interacting entities or individuals, each of which can be described as an autocatalytic network, collectively exhibit cumulative, adaptive, open-ended change, or evolution. Zachar et al.'s critique of SOR stems from misunderstandings; it does not weaken the arguments in (Gabora & Steel, 2021). The formal framework of Reflexively Autocatalytic and foodset-derived sets (RAFs) enables us to model the process whereby, through their interactions, a set of elements become a 'collective self.' SOR shows how the RAF setting provides a means of encompassing abiogenesis and cultural evolution under the same explanatory framework and provides a plausible explanation for the origins of both evolutionary processes. Although SOR allows for detrimental stimuli (and products), there is (naturally) limited opportunity for elements that do not contribute to or reinforce a RAF to become part of it. Replication and cumulative, adaptive change in RAFs is well-established in the literature. Contrary to Zachar et al., SOR is not a pure percolation model (such as SIR); it encompasses not only learning (modeled as assimilation of foodset elements) but also creative restructuring (modeled as generation of foodset-derived elements), as well as the emergence of new structures made possible by new foodset- and foodset-derived elements. Cultural SOR is robust to degradation, and imperfect replication. Zachar et al.'s simulation contains no RAFs, and does not model SOR., Comment: 27 pages, 4 figures. Reply to comment on arXiv:2410.00928

Natural selection successfully explains how organisms accumulate adaptive change despite that traits acquired over a lifetime are eliminated at the end of each generation. However, in some domains that exhibit cumulative, adaptive change -- e.g., cultural evolution, and earliest life -- acquired traits are retained; these domains do not face the problem that Darwin's theory was designed to solve. Lack of transmission of acquired traits occurs when germ cells are protected from environmental change, due to a self-assembly code used in two distinct ways: (i) actively interpreted during development to generate a soma, and (ii) passively copied without interpretation during reproduction to generate germ cells. Early life and cultural evolution appear not to involve a self-assembly code used in these two ways. We suggest that cumulative, adaptive change in these domains is due to a lower-fidelity evolutionary process, and model it using Reflexively Autocatalytic and Foodset-generated networks. We refer to this more primitive evolutionary process as Self-Other Reorganisation (SOR) because it involves internal self-organising and self-maintaining processes within entities, as well as interaction between entities. SOR encompasses learning but in general operates across groups. We discuss the relationship between SOR and Lamarckism, and illustrate a special case of SOR without variation.

The evolutionary relationships between species are typically represented in the biological literature by rooted phylogenetic trees. However, a tree fails to capture ancestral reticulate processes, such as the formation of hybrid species or lateral gene transfer events between lineages, and so the history of life is more accurately described by a rooted phylogenetic network. Nevertheless, phylogenetic networks may be complex and difficult to interpret, so biologists sometimes prefer a tree that summarises the central tree-like trend of evolution. In this paper, we formally investigate methods for transforming an arbitrary phylogenetic network into a tree (on the same set of leaves) and ask which ones (if any) satisfy a simple consistency condition. This consistency condition states that if we add additional species into a phylogenetic network (without otherwise changing this original network) then transforming this enlarged network into a rooted phylogenetic tree induces the same tree on the original set of species as transforming the original network. We show that the LSA (lowest stable ancestor) tree method satisfies this consistency property, whereas several other commonly used methods (and a new one we introduce) do not. We also briefly consider transformations that convert arbitrary phylogenetic networks to another simpler class, namely normal networks., Comment: 11 pages, 4 figures

A wide variety of stochastic models of cladogenesis (based on speciation and extinction) lead to an identical distribution on phylogenetic tree shapes once the edge lengths are ignored. By contrast, the distribution of the tree's edge lengths is generally quite sensitive to the underlying model. In this paper, we review the impact of different model choices on tree shape and edge length distribution, and its impact for studying the properties of phylogenetic diversity (PD) as a measure of biodiversity, and the loss of PD as species become extinct at the present. We also compare PD with a stochastic model of feature diversity, and investigate some mathematical links and inequalities between these two measures plus their predictions concerning the loss of biodiversity under extinction at the present., Comment: 19 pages, 5 figures

In a recent paper, the question of determining the fraction of binary trees that contain a fixed pattern known as the snowflake was posed. We show that this fraction goes to 1, providing two very different proofs: a purely combinatorial one that is quantitative and specific to this problem; and a proof using branching process techniques that is less explicit, but also much more general, as it applies to any fixed patterns and can be extended to other trees and networks. In particular, it follows immediately from our second proof that the fraction of $d$-ary trees (resp. level-$k$ networks) that contain a fixed $d$-ary tree (resp. level-$k$ network) tends to $1$ as the number of leaves grows., Comment: 14 pages 2 figures

It was recently shown that a large class of phylogenetic networks, the `labellable' networks, is in bijection with the set of `expanding' covers of finite sets. In this paper, we show how several prominent classes of phylogenetic networks can be characterised purely in terms of properties of their associated covers. These classes include the tree-based, tree-child, orchard, tree-sibling, and normal networks., Comment: 21 pages, 6 figures. Version 2 fixes an error in Fig 6, clarifies some statements, and corrects some typos

The emergence of an autocatalytic network from an available set of elements is a fundamental step in early evolutionary processes, such as the origin of metabolism. Given a set of elements, the reactions between them (chemical or otherwise), and certain elements catalysing certain reactions, a Reflexively Autocatalytic F-generated (RAF) set is a subset $R'$ of reactions that is self-generating from a given food set, and with each reaction in $R'$ being catalysed from within $R'$. RAF theory has been applied to various phenomena in theoretical biology, and a key feature of the approach is that it is possible to efficiently identify and classify RAFs within large systems. This is possible because RAFs can be described as the (nonempty) subsets of the reactions that are the fixed points of an (efficiently computable) interior map that operates on subsets of reactions. Although the main generic results concerning RAFs can be derived using just this property, we show that for systems with at least 12 reactions there are generic results concerning RAFs that cannot be proven using the interior operator property alone., Comment: 13 pages, 1 figure

In conservation biology, phylogenetic diversity (PD) provides a way to quantify the impact of the current rapid extinction of species on the evolutionary `Tree of Life'. This approach recognises that extinction not only removes species but also the branches of the tree on which unique features shared by the extinct species arose. In this paper, we investigate three questions that are relevant to PD. The first asks how many sets of species of given size $k$ preserve the maximum possible amount of PD in a given tree. The number of such maximum PD sets can be very large, even for moderate-sized phylogenies. We provide a combinatorial characterisation of maximum PD sets, focusing on the setting where the branch lengths are ultrametric (e.g. proportional to time). This leads to a polynomial-time algorithm for calculating the number of maximum PD sets of size $k$ by applying a generating function; we also investigate the types of tree shapes that harbour the most (or fewest) maximum PD sets of size $k$. Our second question concerns optimising a linear function on the species (regarded as leaves of the phylogenetic tree) across all the maximum PD sets of a given size. Using the characterisation result from the first question, we show how this optimisation problem can be solved in polynomial time, even though the number of maximum PD sets can grow exponentially. Our third question considers a dual problem: If $k$ species were to become extinct, then what is the largest possible {\em loss} of PD in the resulting tree? For this question, we describe a polynomial-time solution based on dynamical programming., Comment: 24 pages, 5 figures, 1 table

Polymer models are a widely used tool to study the prebiotic formation of metabolism at the origins of life. Counts of the number of reactions in these models are often crucial in probabilistic arguments concerning the emergence of autocatalytic networks. In the first part of this paper, we provide the first exact description of the number of reactions under widely applied model assumptions. Conclusions from earlier studies rely on either approximations or asymptotic counting, and we show that the exact counts lead to similar, though not always identical, asymptotic results. In the second part of the paper, we investigate a novel model assumption whereby polymers are invariant under spatial rotation. We outline the biochemical relevance of this condition and again give exact enumerative and asymptotic formulae for the number of reactions., Comment: 14 pages, 3 figures. arXiv admin note: substantial text overlap with arXiv:1910.09051

Rooted phylogenetic networks provide a more complete representation of the ancestral relationship between species than phylogenetic trees when reticulate evolutionary processes are at play. One way to reconstruct a phylogenetic network is to consider its `ancestral profile' (the number of paths from each ancestral vertex to each leaf). In general, this information does not uniquely determine the underlying phylogenetic network. A recent paper considered a new class of phylogenetic networks called `orchard networks' where this uniqueness was claimed to hold. Here we show that an additional restriction on the network, that of being `stack-free', is required in order for the original uniqueness claim to hold. On the other hand, if the additional stack-free restriction is lifted, we establish an alternative result; namely, there is uniqueness within the class of orchard networks up to the resolution of vertices of high in-degree., Comment: 18 pages, 4 figures. arXiv admin note: text overlap with arXiv:1901.04064

Attention Schema Theory (AST) is a recent proposal to provide a scientific explanation for the basis of subjective awareness. In AST, the brain constructs a representation of attention taking place in its own (and others') mind (`the attention schema'). Moreover, this representation is incomplete for efficiency reasons. This inherent incompleteness of the attention schema results in the inability of humans to understand how their own subjective awareness arises (related to the so-called `hard problem' of consciousness). Given this theory, the present paper asks whether a mind (either human or machine-based) that incorporates attention, and that contains a representation of its own attention, can ever have a complete representation. Using a simple yet general model and a mathematical argument based on classical topology, we show that a complete representation of attention is not possible, since it cannot faithfully represent streams of attention. In this way, the study supports one of the core aspects of AST, that the brain's representation of its own attention is necessarily incomplete., Comment: 13 pages, 1 figure, (version 5 is a slightly revised version of version 4, which was a moderately revised version of 3 (which was identical to versions 1 and 2, except that the figure was reduced in size to allow easier downloads)

Rooted phylogenetic networks provide a way to describe species' relationships when evolution departs from the simple model of a tree. However, networks inferred from genomic data can be highly tangled, making it difficult to discern the main reticulation signals present. In this paper, we describe a natural way to transform any rooted phylogenetic network into a simpler canonical network, which has desirable mathematical and computational properties, and is based only on the 'visible' nodes in the original network. The method has been implemented and we demonstrate its application to some examples., Comment: 18 pages, 5 figures

The emergence of self-sustaining autocatalytic networks in chemical reaction systems has been studied as a possible mechanism for modelling how living systems first arose. It has been known for several decades that such networks will form within systems of polymers (under cleavage and ligation reactions) under a simple process of random catalysis, and this process has since been mathematically analysed. In this paper, we provide an exact expression for the expected number of self-sustaining autocatalytic networks that will form in a general chemical reaction system, and the expected number of these networks that will also be uninhibited (by some molecule produced by the system). Using these equations, we are able to describe the patterns of catalysis and inhibition that maximise or minimise the expected number of such networks. We apply our results to derive a general theorem concerning the trade-off between catalysis and inhibition, and to provide some insight into the extent to which the expected number of self-sustaining autocatalytic networks coincides with the probability that at least one such system is present., Comment: 16 pages, 1 figure. This version provides more detailed mathematical proofs, a revised figure, and the correction of some minor typos

Tree-child networks are a recently-described class of directed acyclic graphs that have risen to prominence in phylogenetics (the study of evolutionary trees and networks). Although these networks have a number of attractive mathematical properties, many combinatorial questions concerning them remain intractable. In this paper, we show that endowing these networks with a biologically relevant ranking structure yields mathematically tractable objects, which we term ranked tree-child networks (RTCNs). We explain how to derive exact and explicit combinatorial results concerning the enumeration and generation of these networks. We also explore probabilistic questions concerning the properties of RTCNs when they are sampled uniformly at random. These questions include the lengths of random walks between the root and leaves (both from the root to the leaves and from a leaf to the root); the distribution of the number of cherries in the network; and sampling RTCNs conditional on displaying a given tree. We also formulate a conjecture regarding the scaling limit of the process that counts the number of lineages in the ancestry of a leaf. The main idea in this paper, namely using ranking as a way to achieve combinatorial tractability, may also extend to other classes of networks.

Autocatalytic networks have been used to model the emergence of self-organizing structure capable of sustaining life and undergoing biological evolution. Here, we model the emergence of cognitive structure capable of undergoing cultural evolution. Mental representations of knowledge and experiences play the role of catalytic molecules, and interactions amongst them (e.g., the forging of new associations) play the role of reactions, and result in representational redescription. The approach tags mental representations with their source, i.e., whether they were acquired through social learning, individual learning (of pre-existing information), or creative thought (resulting in the generation of new information). This makes it possible to model how cognitive structure emerges, and to trace lineages of cumulative culture step by step. We develop a formal representation of the cultural transition from Oldowan to Acheulean tool technology using Reflexively Autocatalytifc and Food set generated (RAF) networks. Unlike more primitive Oldowan stone tools, the Acheulean hand axe required not only the capacity to envision and bring into being something that did not yet exist, but hierarchically structured thought and action, and the generation of new mental representations: the concepts EDGING, THINNING, SHAPING, and a meta-concept, HAND AXE. We show how this constituted a key transition towards the emergence of semantic networks that were self-organizing, self-sustaining, and autocatalytic, and discuss how such networks replicated through social interaction. The model provides a promising approach to unraveling one of the greatest anthropological mysteries: that of why development of the Acheulean hand axe was followed by over a million years of cultural stasis., Comment: 46 pages; 7 figures; accepted for publication (but not yet published) in Cognitive Science

A key step in the origin of life is the emergence of a primitive metabolism. This requires the formation of a subset of chemical reactions that is both self-sustaining and collectively autocatalytic. A generic theory to study such processes (called 'RAF theory') has provided a precise and computationally effective way to address these questions, both on simulated data and in laboratory studies. One of the classic applications of this theory (arising from Stuart Kauffman's pioneering work in the 1980s) involves networks of polymers under cleavage and ligation reactions; in the first part of this paper, we provide the first exact description of the number of such reactions under various model assumptions. Conclusions from earlier studies relied on either approximations or asymptotic counting, and we show that the exact counts lead to similar (though not always identical) asymptotic results. In the second part of the paper, we solve some questions posed in more recent papers concerning the computational complexity of some key questions in RAF theory. In particular, although there is a fast algorithm to determine whether or not a catalytic reaction network contains a subset that is both self-sustaining and autocatalytic (and, if so, find one), determining whether or not sets exist that satisfy certain additional constraints exist turns out to be NP-complete., Comment: 29 pages, 10 figures

A feature of human creativity is the ability to take a subset of existing items (e.g. objects, ideas, or techniques) and combine them in various ways to give rise to new items, which, in turn, fuel further growth. Occasionally, some of these items may also disappear (extinction). We model this process by a simple stochastic birth--death model, with non-linear combinatorial terms in the growth coefficients to capture the propensity of subsets of items to give rise to new items. In its simplest form, this model involves just two parameters $(P, \alpha)$. This process exhibits a characteristic 'hockey-stick' behaviour: a long period of relatively little growth followed by a relatively sudden 'explosive' increase. We provide exact expressions for the mean and variance of this time to explosion and compare the results with simulations. We then generalise our results to allow for more general parameter assignments, and consider possible applications to data involving human productivity and creativity., Comment: 21 pages, 4 figures

Phylogenetic diversity indices provide a formal way to apportion 'evolutionary heritage' across species. Two natural diversity indices are Fair Proportion (FP) and Equal Splits (ES). FP is also called 'evolutionary distinctiveness' and, for rooted trees, is identical to the Shapley Value (SV), which arises from cooperative game theory. In this paper, we investigate the extent to which FP and ES can differ, characterise tree shapes on which the indices are identical, and study the equivalence of FP and SV and its implications in more detail. We also define and investigate analogues of these indices on unrooted trees (where SV was originally defined), including an index that is closely related to the Pauplin representation of phylogenetic diversity., Comment: 31 pages, 7 figures

Rooted phylogenetic networks provide an explicit representation of the evolutionary history of a set $X$ of sampled species. In contrast to phylogenetic trees which show only speciation events, networks can also accommodate reticulate processes (for example, hybrid evolution, endosymbiosis, and lateral gene transfer). A major goal in systematic biology is to infer evolutionary relationships, and while phylogenetic trees can be uniquely determined from various simple combinatorial data on $X$, for networks the reconstruction question is much more subtle. Here we ask when can a network be uniquely reconstructed from its `ancestral profile' (the number of paths from each ancestral vertex to each element in $X$). We show that reconstruction holds (even within the class of all networks) for a class of networks we call `orchard networks', and we provide a polynomial-time algorithm for reconstructing any orchard network from its ancestral profile. Our approach relies on establishing a structural theorem for orchard networks, which also provides for a fast (polynomial-time) algorithm to test if any given network is of orchard type. Since the class of orchard networks includes tree-sibling tree-consistent networks and tree-child networks, our result generalise reconstruction results from 2008 and 2009. Orchard networks allow for an unbounded number $k$ of reticulation vertices, in contrast to tree-sibling tree-consistent networks and tree-child networks for which $k$ is at most $2|X|-4$ and $|X|-1$, respectively., Comment: 21 pages, 5 figures

In phylogenetic studies, biologists often wish to estimate the ancestral discrete character state at an interior vertex $v$ of an evolutionary tree $T$ from the states that are observed at the leaves of the tree. A simple and fast estimation method --- maximum parsimony --- takes the ancestral state at $v$ to be any state that minimises the number of state changes in $T$ required to explain its evolution on $T$. In this paper, we investigate the reconstruction accuracy of this estimation method further, under a simple symmetric model of state change, and obtain a number of new results, both for 2-state characters, and $r$--state characters ($r>2$). Our results rely on establishing new identities and inequalities, based on a coupling argument that involves a simpler `coin toss' approach to ancestral state reconstruction., Comment: 26 pages, 4 figures

Self-sustaining autocatalytic networks play a central role in living systems, from metabolism at the origin of life, simple RNA networks, and the modern cell, to ecology and cognition. A collectively autocatalytic network that can be sustained from an ambient food set is also referred to more formally as a `Reflexively Autocatalytic F-generated' (RAF) set. In this paper, we first investigate a simplified setting for studying RAFs, which are nevertheless relevant to real biochemistry and allows for a more exact mathematical analysis based on graph-theoretic concepts. This, in turn, allows for the development of efficient (polynomial-time) algorithms for questions that are computationally NP-hard in the general RAF setting. We then show how this simplified setting for RAF systems leads naturally to a more general notion of RAFs that are `generative' (they can be built up from simpler RAFs) and for which efficient algorithms carry over to this more general setting. Finally, we show how classical RAF theory can be extended to deal with ensembles of catalysts as well as the assignment of rates to reactions according to which catalysts (or combinations of catalysts) are available., Comment: 19 pages, 7 figures

A recent paper (Manceau and Lambert, 2016) developed a novel approach for describing two well-defined notions of 'species' based on a phylogenetic tree and a phenotypic partition. In this paper, we explore some further combinatorial properties of this approach and describe an extension that allows an arbitrary number of phenotypic partitions to be combined with a phylogenetic tree for these two species notions., Comment: 19 pages, 5 figures

Given a collection $\tau$ of subsets of a finite set $X$, we say that $\tau$ is {\em phylogenetically flexible} if, for any collection $R$ of rooted phylogenetic trees whose leaf sets comprise the collection $\tau$, $R$ is compatible (i.e. there is a rooted phylogenetic $X$--tree that displays each tree in $R$). We show that $\tau$ is phylogenetically flexible if and only if it satisfies a Hall-type inequality condition of being `slim'. Using submodularity arguments, we show that there is a polynomial-time algorithm for determining whether or not $\tau$ is slim. This `slim' condition reduces to a simpler inequality in the case where all of the sets in $\tau$ have size 3, a property we call `thin'. Thin sets were recently shown to be equivalent to the existence of an (unrooted) tree for which the median function provides an injective mapping to its vertex set; we show here that the unrooted tree in this representation can always be chosen to be a caterpillar tree. We also characterise when a collection $\tau$ of subsets of size 2 is thin (in terms of the flexibility of total orders rather than phylogenies) and show that this holds if and only if an associated bipartite graph is a forest. The significance of our results for phylogenetics is in providing precise and efficiently verifiable conditions under which supertree methods that require consistent inputs of trees, can be applied to any input trees on given subsets of species., Comment: 21 pages, 3 figures

Phylogenetic networks generalise phylogenetic trees and allow for the accurate representation of the evolutionary history of a set of present-day species whose past includes reticulate events such as hybridisation and lateral gene transfer. One way to obtain such a network is by starting with a (rooted) phylogenetic tree $T$, called a base tree, and adding arcs between arcs of $T$. The class of phylogenetic networks that can be obtained in this way is called tree-based networks and includes the prominent classes of tree-child and reticulation-visible networks. Initially defined for binary phylogenetic networks, tree-based networks naturally extend to arbitrary phylogenetic networks. In this paper, we generalise recent tree-based characterisations and associated proximity measures for binary phylogenetic networks to arbitrary phylogenetic networks. These characterisations are in terms of matchings in bipartite graphs, path partitions, and antichains. Some of the generalisations are straightforward to establish using the original approach, while others require a very different approach. Furthermore, for an arbitrary tree-based network $N$, we characterise the support trees of $N$, that is, the tree-based embeddings of $N$. We use this characterisation to give an explicit formula for the number of support trees of $N$ when $N$ is binary. This formula is written in terms of the components of a bipartite graph., Comment: 20 pages, 6 figures

It is a classical result that an unrooted tree $T$ having positive real-valued edge lengths and no vertices of degree two can be reconstructed from the induced distance between each pair of leaves. Moreover, if each non-leaf vertex of $T$ has degree 3 then the number of distance values required is linear in the number of leaves. A canonical candidate for such a set of pairs of leaves in $T$ is the following: for each non-leaf vertex $v$, choose a leaf in each of the three components of $T-v$, group these three leaves into three pairs, and take the union of this set over all choices of $v$. This forms a so-called 'triplet cover' for $T$. In the first part of this paper we answer an open question (from 2012) by showing that the induced leaf-to-leaf distances for any triplet cover for $T$ uniquely determine $T$ and its edge lengths. We then investigate the finer combinatorial properties of triplet covers. In particular, we describe the structure of triplet covers that satisfy one or more of the following properties of being minimal, 'sparse', and 'shellable'., Comment: 32 pages, 5 figures

It has been proposed that cultural evolution was made possible by a cognitive transition brought about by onset of the capacity for self-triggered recall and rehearsal. Here we develop a novel idea that models of collectively autocatalytic networks, developed for understanding the origin and organization of life, may also help explain the origin of the kind of cognitive structure that makes cultural evolution possible. In our setting, mental representations (for example, memories, concepts, ideas) play the role of 'molecules', and 'reactions' involve the evoking of one representation by another through remindings, associations, and stimuli. In the 'episodic mind', representations are so coarse-grained (encode too few properties) that such reactions are catalyzed only by external stimuli. As cranial capacity increased, representations became more fine-grained (encoded more features), allowing them to act as catalysts, leading to streams of thought. At this point, the mind could combine representations and adapt them to specific needs and situations, and thereby contribute to cultural evolution. In this paper, we propose and study a simple and explicit cognitive model that gives rise naturally to autocatylatic networks, and thereby provides a possible mechanism for the transition from a pre-cultural episodic mind to a mimetic mind., Comment: 28 pages, 2 figures

Phylogenetic inference aims to reconstruct the evolutionary relationships of different species based on genetic (or other) data. Discrete characters are a particular type of data, which contain information on how the species should be grouped together. However, it has long been known that some characters contain more information than others. For instance, a character that assigns the same state to each species groups all of them together and so provides no insight into the relationships of the species considered. At the other extreme, a character that assigns a different state to each species also conveys no phylogenetic signal. In this manuscript, we study a natural combinatorial measure of the information content of an individual character and analyse properties of characters that provide the maximum phylogenetic information, particularly, the number of states such a character uses and how the different states have to be distributed among the species or taxa of the phylogenetic tree., Comment: 16 pages, 7 figures. Final version has now appeared in Journal of Mathematical Biology (December 2017) https://link.springer.com/article/10.1007/s00285-017-1198-2

The reconstruction of phylogenetic trees from discrete character data typically relies on models that assume the characters evolve under a continuous-time Markov process operating at some overall rate $\lambda$. When $\lambda$ is too high or too low, it becomes difficult to distinguish a short interior edge from a polytomy (the tree that results from collapsing the edge). In this note, we investigate the rate that maximizes the expected log-likelihood ratio (i.e. the Kullback--Leibler separation) between the four-leaf unresolved (star) tree and a four-leaf binary tree with interior edge length $\epsilon$. For a simple two-state model, we show that as $\epsilon$ converges to $0$ the optimal rate also converges to zero when the four pendant edges have equal length. However, when the four pendant branches have unequal length, two local optima can arise, and it is possible for the globally optimal rate to converge to a non-zero constant as $\epsilon \rightarrow 0$. Moreover, in the setting where the four pendant branches have equal lengths and either (i) we replace the two-state model by an infinite-state model or (ii) we retain the two-state model and replace the Kullback--Leibler separation by Euclidean distance as the maximization goal, then the optimal rate also converges to a non-zero constant., Comment: 12 pages, 5 figures

Phylogenetic networks are a type of directed acyclic graph that represent how a set $X$ of present-day species are descended from a common ancestor by processes of speciation and reticulate evolution. In the absence of reticulate evolution, such networks are simply phylogenetic (evolutionary) trees. Moreover, phylogenetic networks that are not trees can sometimes be represented as phylogenetic trees with additional directed edges placed between their edges. Such networks are called {\em tree based}, and the class of phylogenetic networks that are tree based has recently been characterised. In this paper, we establish a number of new characterisations of tree-based networks in terms of path partitions and antichains (in the spirit of Dilworth's theorem), as well as via matchings in a bipartite graph. We also show that a temporal network is tree based if and only if it satisfies an antichain-to-leaf condition. In the second part of the paper, we define three indices that measure the extent to which an arbitrary phylogenetic network deviates from being tree based. We describe how these three indices can be described exactly and computed efficiently using classical results concerning maximum-sized matchings in bipartite graphs., Comment: 15 pages, 5 figures

Consensus methods are widely used for combining phylogenetic trees into a single estimate of the evolutionary tree for a group of species. As more taxa are added, the new source trees may begin to tell a different evolutionary story when restricted to the original set of taxa. However, if the new trees, restricted to the original set of taxa, were to agree exactly with the earlier trees, then we might hope that their consensus would either agree with or resolve the original consensus tree. In this paper, we ask under what conditions consensus methods exist that are 'future proof' in this sense. While we show that some methods (e.g. Adams consensus) have this property for specific types of input, we also establish a rather surprising `no-go' theorem: there is no 'reasonable' consensus method that satisfies the future-proofing property in general. We then investigate a second notion of 'future proofing' for consensus methods, in which trees (rather than taxa) are added, and establish some positive and negative results. We end with some questions for future work., Comment: 15 pages, 5 figures

Trees with labelled leaves and with all other vertices of degree three play an important role in systematic biology and other areas of classification. A classical combinatorial result ensures that such trees can be uniquely reconstructed from the distances between the leaves (when the edges are given any strictly positive lengths). Moreover, a linear number of these pairwise distance values suffices to determine both the tree and its edge lengths. A natural set of pairs of leaves is provided by any `triplet cover' of the tree (based on the fact that each non-leaf vertex is the median vertex of three leaves). In this paper we describe a number of new results concerning triplet covers of minimum size. In particular, we characterize such covers in terms of an associated graph being a 2-tree. Also, we show that minimum triplet covers are `shellable' and thereby provide a set of pairs for which the inter-leaf distance values will uniquely determine the underlying tree and its associated branch lengths., Comment: 11 pages, 4 figures

All living systems -- from the origin of life to modern cells -- rely on a set of biochemical reactions that are simultaneously self-sustaining and autocatalytic. This notion of an autocatalytic set has been formalized graph-theoretically (as `RAF'), leading to mathematical results and polynomial-time algorithms that have been applied to simulated and real chemical reaction systems. In this paper, we investigate the emergence of autocatalytic sets in polymer models when the catalysis rate of each molecule type is drawn from some probability distribution. We show that although the average catalysis rate $f$ for RAFs to arise depends on this distribution, a universal linear upper and lower bound for $f$ (with increasing system size) still applies. However, the probability of the appearance (and size) of autocatalytic sets can vary widely, depending on the particular catalysis distribution. We use simulations to explore how tight the mathematical bounds are, and the reasons for the observed variations. We also investigate the impact of inhibition (where molecules can also inhibit reactions) on the emergence of autocatalytic sets, deriving new mathematical and algorithmic results., Comment: 21 pages, 6 figures, 4 tables

The reconstruction of phylogenetic trees from molecular sequence data relies on modelling site substitutions by a Markov process, or a mixture of such processes. In general, allowing mixed processes can result in different tree topologies becoming indistinguishable from the data, even for infinitely long sequences. However, when the underlying Markov process supports linear phylogenetic invariants, then provided these are sufficiently informative, the identifiability of the tree topology can be restored. In this paper, we investigate a class of processes that support linear invariants once the stationary distribution is fixed, the `equal input model'. This model generalizes the `Felsenstein 1981' model (and thereby the Jukes--Cantor model) from four states to an arbitrary number of states (finite or infinite), and it can also be described by a `random cluster' process. We describe the structure and dimension of the vector spaces of phylogenetic mixtures and of linear invariants for any fixed phylogenetic tree (and for all trees -- the so called `model invariants'), on any number $n$ of leaves. We also provide a precise description of the space of mixtures and linear invariants for the special case of $n=4$ leaves. By combining techniques from discrete random processes and (multi-) linear algebra, our results build on a classic result that was first established by James Lake in 1987., Comment: 25 pages, 1 figure, to appear in Journal of Mathematical Biology

A central theme in phylogenetics is the reconstruction and analysis of evolutionary trees from a given set of data. To determine the optimal search methods for reconstructing trees, it is crucial to understand the size and structure of the neighbourhoods of trees under tree rearrangement operations. The diameter and size of the immediate neighbourhood of a tree has been well-studied, however little is known about the number of trees at distance two, three or (more generally) $k$ from a given tree. In this paper we provide a number of exact and asymptotic results concerning these quantities, and identify some key aspects of tree shape that play a role in determining these quantities. We obtain several new results for two of the main tree rearrangement operations - Nearest Neighbour Interchange and Subtree Prune and Regraft -- as well as for the Robinson-Foulds metric on trees., Comment: 41 pages

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., Comment: 17 pages, 5 figures

Statistically consistent estimation of phylogenetic trees or gene trees is possible if pairwise sequence dissimilarities can be converted to a set of distances that are proportional to the true evolutionary distances. Susko et al. (2004) reported some strikingly broad results about the forms of inconsistency in tree estimation that can arise if corrected distances are not proportional to the true distances. They showed that if the corrected distance is a concave function of the true distance, then inconsistency due to long branch attraction will occur. If these functions are convex, then two "long branch repulsion" trees will be preferred over the true tree -- though these two incorrect trees are expected to be tied as the preferred true. Here we extend their results, and demonstrate the existence of a tree shape (which we refer to as a "twisted Farris-zone" tree) for which a single incorrect tree topology will be guaranteed to be preferred if the corrected distance function is convex. We also report that the standard practice of treating gaps in sequence alignments as missing data is sufficient to produce non-linear corrected distance functions if the substitution process is not independent of the insertion/deletion process. Taken together, these results imply inconsistent tree inference under mild conditions. For example, if some positions in a sequence are constrained to be free of substitutions and insertion/deletion events while the remaining sites evolve with independent substitutions and insertion/deletion events, then the distances obtained by treating gaps as missing data can support an incorrect tree topology even given an unlimited amount of data., Comment: 29 pages, 3 figures