Search PubMed⌕ Search

Biomedical subjects

Mike Steel

Publications and source records attributed to Mike Steel.

16 recordsLinked to original sources
PubMed2006

Neighbor-joining revealed.

It is nearly 20 years since the landmark paper (Saitou and Nei 1987) in Molecular Biology and Evolution introducing Neighbor-Joining (NJ). The method has become the most widely used method for building phylogenetic trees from distances, and the original paper has been cited about 13,000 times (Science Citation Index). Yet the question "what does the NJ method seek to do?" has until recently proved somewhat elusive, leading to some imprecise claims and misunderstanding. However, a rigorous answer to this question has recently been provided by further mathematical investigation, and the purpose of this note is to highlight these results and their significance for interpreting NJ. The origins of this story lie in a paper by Pauplin (2000) though its continuation has unfolded in more mathematically inclined literature. Our aim here is to make these findings more widely accessible.

Algorithms↗
PubMed2006

Hybrids in real time.

We describe some new and recent results that allow for the analysis and representation of reticulate evolution by non-tree networks. In particular, we (1) present a simple result to show that, despite the presence of reticulation, there is always a well-defined underlying tree that corresponds to those parts of life that do not have a history of reticulation; (2) describe and apply new theory for determining the smallest number of hybridization events required to explain conflicting gene trees; and (3) present a new algorithm to determine whether an arbitrary rooted network can be realized by contemporaneous reticulation events. We illustrate these results with examples. [Directed acyclic graph; reticulate evolution; hybrid species; sub-tree prune and re-graft.].

Biological Evolution↗
PubMed2006

Maximizing phylogenetic diversity in biodiversity conservation: Greedy solutions to the Noah's Ark problem.

The Noah's Ark Problem (NAP) is a comprehensive cost-effectiveness methodology for biodiversity conservation that was introduced by Weitzman (1998) and utilizes the phylogenetic tree containing the taxa of interest to assess biodiversity. Given a set of taxa, each of which has a particular survival probability that can be increased at some cost, the NAP seeks to allocate limited funds to conserving these taxa so that the future expected biodiversity is maximized. Finding optimal solutions using this framework is a computationally difficult problem to which a simple and efficient "greedy" algorithm has been proposed in the literature and applied to conservation problems. We show that, although algorithms of this type cannot produce optimal solutions for the general NAP, there are two restricted scenarios of the NAP for which a greedy algorithm is guaranteed to produce optimal solutions. The first scenario requires the taxa to have equal conservation cost; the second scenario requires an ultrametric tree. The NAP assumes a linear relationship between the funding allocated to conservation of a taxon and the increased survival probability of that taxon. This relationship is briefly investigated and one variation is suggested that can also be solved using a greedy algorithm.

Algorithms↗
PubMed2005

Reconstructing pedigrees: a combinatorial perspective.

A pedigree is a directed graph that displays the relationship between individuals according to their parentage. We derive a combinatorial result that shows how any pedigree-up to individuals who have no extant (present-day) ancestors-can be reconstructed from (sex-labelled) pedigrees that describe the ancestry of single extant individuals and pairs of extant individuals. Furthermore, this reconstruction can be done in polynomial time. We also provide an example to show that the corresponding reconstruction result does not hold for pedigrees that are not sex-labelled. We then show how any pedigree can also be reconstructed from two functions that just describe certain circuits in the pedigree. Finally, we obtain an enumeration result for pedigrees that is relevant to the question of how many segregating sites are needed to reconstruct pedigrees.

Animals↗
PubMed2005

Random biochemical networks: the probability of self-sustaining autocatalysis.

We determine conditions under which a random biochemical system is likely to contain a subsystem that is both autocatalytic and able to survive on some ambient 'food' source. Such systems have previously been investigated for their relevance to origin-of-life models. In this paper we extend earlier work, by finding precisely the order of catalysation required for the emergence of such self-sustaining autocatalytic networks. This answers questions raised in earlier papers, yet also allows for a more general class of models. We also show that a recently described polynomial-time algorithm for determining whether a catalytic reaction system contains an autocatalytic, self-sustaining subsystem is unlikely to adapt to allow inhibitory catalysation--in this case we show that the associated decision problem is NP-complete.

Biochemical Phenomena↗
PubMed2005

Should phylogenetic models be trying to "fit an elephant"?

For the past two decades, there has been an ongoing debate within the plylogenetics community over whether model-based approaches for molecular systematics (such as maximum likelihood) should be preferred over the more traditional "maximum parsimony" approach. A recent simulation study by Kolaczkowski and Thornton has brought this debate into sharp focus. In this article, I discuss the significance of their findings and offer a prognosis on the implications for molecular phylogenetics. I believe that biochemistry and model selection have an important role in developing accurate phylogenetic approaches.

Animals↗
PubMed2005

Phylogenetic diversity and the greedy algorithm.

Given a phylogenetic tree with leaves labeled by a collection of species, and with weighted edges, the "phylogenetic diversity" of any subset of the species is the sum of the edge weights of the minimal subtree connecting the species. This measure is relevant in biodiversity conservation where one may wish to compare different subsets of species according to how much evolutionary variation they encompass. In this note we show that phylogenetic diversity has an attractive mathematical property that ensures that we can solve the following problem easily by the greedy algorithm: find a subset of the species of any given size k of maximal phylogenetic diversity. We also describe an extension of this result that also allows weights to be assigned to species.

Algorithms↗
PubMed2004

Detecting autocatalytic, self-sustaining sets in chemical reaction systems.

The ability of systems of molecular reactions to be simultaneously autocatalylic and sustained by some ambient 'food source' of simple molecules may have been an essential step in the origin of life. In this paper we first describe a polynomial-time algorithm that determines whether any given set of molecules, reactions and catalysations contains a subsystem that is both autocatalytic and able to be sustained from a given subset of the molecules. We also describe some combinatorial properties of this algorithm, and show how it can be used to find irreducible auto-catalysing and sustaining subsystems. In the second part of the paper we use the algorithm to investigate random catalytic networks-in particular, a model described by Kauffman. Using simulations and some analytic techniques we investigate the rate of catalysis that is required for the emergence of autocatalytic and sustaining subsystems.

Algorithms↗
PubMed2004

Supertree algorithms for ancestral divergence dates and nested taxa.

MOTIVATION: Supertree methods have been often identified as a possible approach to the reconstruction of the 'Tree of Life'. However, a limitation of such methods is that, typically, they use just leaf-labelled phylogenetic trees to infer the resulting supertree. RESULTS: In this paper, we describe several new supertree algorithms that extend the allowable information that can be used for phylogenetic inference. These algorithms have been recently implemented and we describe here two illustrative applications. AVAILABILITY: These new algorithms are freely available for application at http://darwin.zoology.gla.ac.uk/cgi-bin/build.pl.

Algorithms↗
PubMed2004

Phylogenetic trees based on gene content.

UNLABELLED: Comparing gene content between species can be a useful approach for reconstructing phylogenetic trees. In this paper, we derive a maximum-likelihood estimation of evolutionary distance between species under a simple model of gene genesis and gene loss. Using simulated data on a biological tree with 107 taxa (and on a number of randomly generated trees), we compare the accuracy of tree reconstruction using this ML distance measure to an earlier ad hoc distance. We then compare these distance-based approaches to a character-based tree reconstruction method (Dollo parsimony) which seems well suited to the analysis of gene content data. To simplify simulations, we give a formal proof of the well-known 'fact' that the Dollo parsimony score is independent of the choice of root. Our results show a consistent trend, with the character-based method and ML distance measure outperforming the earlier ad hoc distance method. AVAILABILITY: http://www.ab.informatik.uni-tuebingen.de/software/genecontent/welcome_en.html

Algorithms↗
PubMed2004

A phase transition for a random cluster model on phylogenetic trees.

We investigate a simple model that generates random partitions of the leaf set of a tree. Of particular interest is the reconstruction question: what number k of independent samples (partitions) are required to correctly reconstruct the underlying tree (with high probability)? We demonstrate a phase transition for k as a function of the mutation rate, from logarithmic to polynomial dependence on the size of the tree. We also describe a simple polynomial-time tree reconstruction algorithm that applies in the logarithmic region. This model and the associated reconstruction questions are motivated by a Markov model for genomic evolution in molecular biology.

Cluster Analysis↗
PubMed2004

Distances that perfectly mislead.

Given a collection of discrete characters (e.g., aligned DNA sites, gene adjacencies), a common measure of distance between taxa is the proportion of characters for which taxa have different character states. Tree reconstruction based on these (uncorrected) distances can be statistically inconsistent and can lead to trees different from those obtained using character-based methods such as maximum likelihood or maximum parsimony. However, in these cases the distance data often reveal their unreliability by some deviation from additivity, as indicated by conflicting support for more than one tree. We describe two results that show how uncorrected (and miscorrected) distance data can be simultaneously perfectly additive and misleading. First, multistate character data can be perfectly compatible and define one tree, and yet the uncorrected distances derived from these characters are perfectly treelike (and obey a molecular clock), only for a completely different tree. Second, under a Markov model of character evolution a similar phenomenon can occur; not only is there statistical inconsistency using uncorrected distances, but there is no evidence of this inconsistency because the distances look perfectly treelike (this does not occur in the classic two-parameter Felsenstein zone). We characterize precisely when uncorrected distances are additive on the true (and on a false) tree for four taxa. We also extend this result to a more general setting that applies to distances corrected according to an incorrect model.

Classification↗
PubMed2002

Some statistical aspects of the maximum parsimony method.

The last three decades have seen considerable debate concerning the relative merits and problems associated with two competing approaches to phylogeny--approaches based on the parsimony principle versus maximum likelihood methodology. Although the two approaches may seem quite opposed, there are in fact some close relationships between them. For example, we describe a recent result that shows how maximum parsimony can be regarded as a type of maximum likelihood estimator when there is no common mechanism between sites (such as might occur with morphological data and certain forms of molecular data). Distinguishing between this and other implementations of maximum likelihood helps clarify some of the dispute that has surrounded the two methodologies. We also provide a brief overview of some mathematical and statistical properties of the maximum parsimony criterion.

Likelihood Functions↗
PubMedDate not supplied

Unicyclic networks: compatibility and enumeration.

Graphs obtained from a binary leaf labeled ("phylogenetic") tree by adding an edge so as to introduce a cycle provide a useful representation of hybrid evolution in molecular evolutionary biology. This class of graphs (which we call "unicyclic networks") also has some attractive combinatorial properties, which we present. We characterize when a set of binary phylogenetic trees is displayed by a unicyclic network in terms of tree rearrangement operations. This leads to a triple-wise compatibility theorem and a simple, fast algorithm to determine 1-cycle compatibility. We also use generating function techniques to provide closed-form expressions that enumerate unicyclic networks with specified or unspecified cycle length, and we provide an extension to enumerate a class of multicyclic networks.

Algorithms↗