In studies of molecular evolution, one is typically confronted with the task of inferring a phylogenetic tree from a set X of sequences of length n over a finite alphabet Λ. For studies that invoke parsimony, it has been found helpful to consider the quasi-median graph generated by X in the Hamming graph Λn. Although a great deal is already known about quasi-median graphs (and their algebraic counterparts), little is known about the quasi-median generation in Λn starting from a set X of vertices. We describe the vertices of the quasi-median graph generated by X in terms of the coordinatewise partitions of X. In particular, we clarify when the generated quasi-median graph is the so-called relation graph associated with X. This immediately characterizes the instances where either a block graph or the total Hamming graph is generated.

Mid Sweden University, Faculty of Science, Technology and Media, Department of Engineering, Physics and Mathematics.

Moulton, Vincent

Mid Sweden University, Faculty of Science, Technology and Media, Department of Engineering, Physics and Mathematics.

Connectivity calculus2003In: Applied Mathematics Letters, ISSN 0893-9659, E-ISSN 1873-5452, Vol. 16, no 3, p. 395-399Article in journal (Refereed)

Abstract [en]

Given a finite hypergraph H = (V, E) and, for each e E E, a collection of nonempty subsets pi(e) of e, Mobius inversion is used to establish a recursive formula for the number of connected components of the hypergraph H = (V, boolean OR(eis an element ofE)pi(e)). As shown elsewhere, this formula is an essential ingredient in the context of a certain divide-and-conquer strategy that allows us to define a dynamical programming scheme solving Steiner's problem for graphs in linear time (however, with a constant depending hyperexponentially on their tree width).

3. Dress, A.

et al.

Huber, K. T.

Mid Sweden University, Faculty of Science, Technology and Media, Department of Engineering, Physics and Mathematics.

Moulton, Vincent

Mid Sweden University, Faculty of Science, Technology and Media, Department of Engineering, Physics and Mathematics.

Mid Sweden University, Faculty of Science, Technology and Media, Department of Engineering, Physics and Mathematics.

Moulton, Vincent

Mid Sweden University, Faculty of Science, Technology and Media, Department of Engineering, Physics and Mathematics.

Antipodal metrics and split systems2002In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 23, no 2, p. 187-200Article in journal (Refereed)

Abstract [en]

Recall that a metric d on a finite set X is called antipodal if there exists a map sigma : X --> X: x --> (x) over bar so that d(x, (x) over bar) = d(x, y) + d(y, (x) over bar) holds for all x, y epsilon X. Antipodal metrics canonically arise as metrics induced on specific weighted graphs, although their abundance becomes clearer in light of the fact that any finite metric space can be isometrically embedded in a more or less canonical way into an antipodal metric space called its full antipodal extension. In this paper, we examine in some detail antipodal metrics that are, in addition, totally split decomposable. In particular, we give an explicit characterization of such metrics, and prove that-somewhat surprisingly-the full antipodal extension of a proper metric d on a finite set X is totally split decomposable if and only if d is linear or #X = 3 holds.

Institute of Fundamental Sciences, Massey University, Private Bag 11 222, Palmerston North, New Zealand.

Moulton, Vincent

Mid Sweden University, Faculty of Science, Technology and Media, Department of Engineering, Physics and Mathematics.

The relation graph2002In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 244, no 1-3, p. 153-166Article in journal (Refereed)

Abstract [en]

Given a set R of distinct, non-trivial partitions of a finite set, we define the relation graph G(R) of R. In case R consists only of bipartitions, G(R) is the well-known Buneman graph, a median graph that has applications in the area of phylogenetic analysis., Here we consider properties of the relation graph for general sets of partitions and, in particular, we see that it mimics the behaviour of the Buneman graph by proving the following two theorems:(i) The graph G(R) is a Hamming graph if and only if R is strongly incompatible.(ii) The graph G(R) is a block graph with #R blocks if and only if R is strongly compatible.

The groupings of taxa in a phylogenetic tree cannot represent all the conflicting signals that usually occur among site patterns in aligned homologous genetic sequences. Hence a tree-building program must compromise by reporting a subset of the patterns, using some discriminatory criterion. Thus, in the worst case, out of possibly a large number of equally good trees, only an arbitrarily chosen tree might be reported by the tree-building program as “The Tree.” This tree might then be used as a basis for phylogenetic conclusions. One strategy to represent conflicting patterns in the data is to construct a network. The Buneman graph is a theoretically very attractive example of such a network. In particular, a characterization for when this network will be a tree is known. Also the Buneman graph contains each of the most parsimonious trees indicated by the data. In this paper we describe a new method for constructing the Buneman graph that can be used for a generalization of Hadamard conjugation to networks. This new method differs from previous methods by allowing us to focus on local regions of the graph without having to first construct the full graph. The construction is illustrated by an example.

Observations from molecular marker studies on recently diverged species indicate that substitution patterns in DNA sequences can often be complex and poorly described by tree-like bifurcating evolutionary models. These observations might result from processes of-species diversification and/or processes of sequence evolution that are not tree-like. In these Cases, bifurcating tree representations provide poor visualization of phylogenetic signals in sequence data. In this paper, we use median networks to study DNA sequence substitution patterns in plant nuclear and chloroplast markers. We describe how to prune median networks to obtain so called pruned median networks. These simpler networks may help to provide a useful framework for investigating the phylogenetic complexity of recently diverged taxa with hybrid origins.