On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance

The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees.Received March 16, 2004     

Cyclic permutations and evolutionary trees

Given a tree with leaf set X, there are certain ways of arranging the elements of X in a circular order so that can be embedded in the plane and ‘preserve’ this ordering. We investigate some new combinatorial properties of these ‘circular orderings.’ We then use these properties to establish two results concerning dissimilarity maps on X that are induced by edge-weighted trees with leaf set X.     

Identifying phylogenetic trees

A central problem that arises in evolutionary biology is that of displaying partitions of subsets of a finite set X on a tree whose vertices are partially labelled with the elements of X. Such a tree is called an X-tree and, for a collection of partitions of subsets of X, characterisations for the existence and uniqueness of an X-tree that displays have been previously given in terms of chordal graphs. In this paper, we obtain two closely related characterisations also in terms of chordal graphs. The first describes when identifies an X-tree, and the second describes when a compatible subset of is of maximum size.     

N-labelling studies of the reaction of 2,6-di-t-butyl-4-methyl-4-nitrocyclohexa-2,5-dienone with nitrogen dioxide; A revised mechanism

Reaction of the ¹⁵N-4-nitrodienone (1) with excess nitrogen dioxide in benzene for 16 h gives the 4,5,6-trinitro ketone (2), labelled (¹⁵NO₂) at C6 but not at C4, and recovered 4-nitrodienone (1) in which extensive loss of ¹⁵NO₂ has occurred. The mechanistic implications of these and related results are discussed.     

Multiple nitrene insertions into metal-sulfur bonds of dithiocarbamate complexes: synthesis of sulfido-amido and zwitterionic tetraamido complexes

The iodine(III) reagent, PhI[double bond, length as m-dash]NTs, acts as a source of the nitrene fragment NTs, which undergoes facile insertion into the metal-sulfur bonds of a range of dithiocarbamate complexes. Addition of two equivalents of PhI=NTs to [M(S(2)CNR2)2] affords sulfido-amido complexes [M{SC(NR2)SNTs}2](M=Ni, Cu), which insert two further nitrene fragments to afford zwitterionic tetraamido complexes [M{TsNSC(NR2)SNTs}2](M=Co, Ni, Cu). Crystallographic studies have been carried out on both types of complex allowing possible resonance hydrids of the new ligand types to be assessed.     

High-performance liquid chromatographic analysis of free long chain fatty acids produced during lipolysis by anaerobic digestor sludge

The development of sample extraction techniques in conjunction with application of a modified version of an established HPLC technique allowed the rapid estimation of concentrations of long chain fatty acids (LCFA) produced by the lipolytic activity of bacteria in anaerobic digestor sludges or experiments using the sludges as inocula. It was established that free long chain fatty acids will preferentially partition into certain phases in the sludge or experimental cultures. These data, and application of the developed techniques for monitoring of LCFA, may lead to the avoidance of toxicity and failure of full-scale anaerobic digestors treating high lipid content waste in the future.     

An optimal two-step quadratic spline collocation method for the Dirichlet biharmonic problem

Numerical Algorithms - A two-step quadratic spline collocation method is formulated for the solution of the Dirichlet biharmonic problem on the unit square rewritten as a coupled system of two...