
HansJürgen Bandelt and
Arne Dür. Translating DNA data tables into quasimedian networks for parsimony analysis and error detection. In MPE, Vol. 42(1):256271, 2007. Keywords: abstract network, from sequences, parsimony, phylogenetic network, phylogeny, quasimedian network, reconstruction. Note: http://dx.doi.org/10.1016/j.ympev.2006.07.013.
Toggle abstract
"Every DNA data table can be turned into a quasimedian network that faithfully represents the data. We show that for (weighted) condensed data tables the associated network harbors all most parsimonious reconstructions for any tree that connects the sampled haplotypes. Structural features of this network can be computed directly from the data table. The key principle repeatedly used is that the quasimedian network is uniquely determined by the subtables for pairs of characters. The translation of a table into a network enhances the understanding of the properties of the data in regard to homoplasy and potential artifacts. The total number of nodes of such a network measures the complexity of the data. In particular, networks that display the results of filter analyses by which hotspot mutations are removed help to detect data idiosyncrasies and thus pinpoint sequencing problems. A pertinent example drawn from human mtDNA illustrates these points. © 2006 Elsevier Inc. All rights reserved."



HansJürgen Bandelt,
Vincent Macaulay and
Martin Richards. Median networks: speedy construction and greedy reduction, one simulation, and two case studies from human mtDNA. In MPE, Vol. 16:828, 2000. Keywords: from sequences, from splits, median network, phylogenetic network, phylogeny, reconstruction. Note: http://www.stats.gla.ac.uk/~vincent/papers/speedy.pdf.
Toggle abstract
"Molecular data sets characterized by few phylogenetically informative characters with a broad spectrum of mutation rates, such as intraspecific controlregion sequence variation of human mitochondrial DNA (mtDNA), can be usefully visualized in the form of median networks. Here we provide a stepbystep guide to the construction of such networks by hand. We improve upon a previously implemented algorithm by outlining an efficient parametrized strategy amenable to large data sets, greedy reduction, which makes it possible to reconstruct some of the confounding recurrent mutations. This entails some postprocessing as well, which assists in capturing more parsimonious solutions. To simplify the creation of the resulting network by hand, we describe a speedy approach to network construction, based on a careful planning of the processing order. A coalescent simulation tailored to human mtDNA variation in Eurasia testifies to the usefulness of reduced median networks, while highlighting notorious problems faced by all phylogenetic methods in this context. Finally, we discuss two case studies involving the comparison of characters in the two hypervariable segments of the human mtDNA control region in the light of the worldwide controlregion sequence database, as well as additional restriction fragment length polymorphism information. We conclude that only a minority of the mutations that hit the second segment occur at sites that would have a mutation rate comparable to those at most sites in the first segment. Discarding the known 'noisy' sites of the second segment enhances the analysis. (C) 2000 Academic Press."









HansJürgen Bandelt and
Andreas W. M. Dress. An order theoretic framework for overlapping clustering. In DM, Vol. 136(13):2137, 1994.
Toggle abstract
"Cluster analysis deals with procedures which  given a finite collection X of objects together with some kind of local dissimilarity information  identify those subcollections C of objects from X, called clusters, which exhibit a comparatively low degree of internal dissimilarity. In this note we study arbitrary mappings φ which assign to each subcollection A ⊆ X of objects its internal degree of dissimilarity φ (A), subject only to the natural condition that A ⊆ B ⊆ X implies φ (A) ̌ φ (B), and we analyse on a rather abstract, purely order theoretic level how assumptions concerning the way such a mapping φ might be constructed from local data (that is, data involving only a few objects at a time) influence the degree of overlapping observed within the resulting family of clusters,  and vice versa. Hence, unlike previous order theoretic approaches to cluster analysis, we do not restrict our attention to nonoverlapping, hierarchical clustering. Instead, we regard a dissimilarity function φ as an arbitrary isotone mapping from a finite partially ordered set I  e.g. the set P(X) of all subsets A of a finite set X  into a (partially) ordered set R  e.g. the nonnegative real numbers  and we study the correspondence between the two subsets C(φ) and D(φ) of I, formed by the elements whose images are inaccessible from above and from below, respectively. While D(φ) constitutes the local data structure from which φ can be built up, C(φ) embodies the family of clusters associated with φ. Our results imply that in case I: = P(X) and R: = R≥0 one has # D ̌ n for all Dε{lunate}D(φ) and some fixed nε{lunate}N if and only if{A figure is presented} for all C0,..., Cnε{lunate}C(φ) if and only if this holds for all subsets C0,..., Cn ⊆ X, generalizing a wellknown criterion for nconformity of hypergraphs as well as corresponding results due to Batbedat, dealing with the case n = 2. © 1994."



HansJürgen Bandelt and
Andreas W. M. Dress. A canonical decomposition theory for metrics on a finite set. In Advances in Mathematics, Vol. 92(1):47105, 1992. Keywords: abstract network, circular split system, from distances, split, split decomposition, split network, weak hierarchy, weakly compatible.
Toggle abstract
"We consider specific additive decompositions d = d1 + ... + dn of metrics, defined on a finite set X (where a metric may give distance zero to pairs of distinct points). The simplest building stones are the slit metrics, associated to splits (i.e., bipartitions) of the given set X. While an additive decomposition of a Hamming metric into split metrics is in no way unique, we achieve uniqueness by restricting ourselves to coherent decompositions, that is, decompositions d = d1 + ... + dn such that for every map f:X → R with f(x) + f(y) ≥ d(x, y) for all x, y ε{lunate} X there exist maps f1, ..., fn: X → R with f = f1 + ... + fn and fi(x) + fi(y) ≥ di(x, y) for all i = 1,..., n and all x, y ε{lunate} X. These coherent decompositions are closely related to a geometric decomposition of the injective hull of the given metric. A metric with a coherent decomposition into a (weighted) sum of split metrics will be called totally splitdecomposable. Tree metrics (and more generally, the sum of two tree metrics) are particular instances of totally splitdecomposable metrics. Our main result confirms that every metric admits a coherent decomposition into a totally splitdecomposable metric and a splitprime residue, where all the split summands and hence the decomposition can be determined in polynomial time, and that a family of splits can occur this way if and only if it does not induce on any fourpoint subset all three splits with block size two. © 1992."





HansJürgen Bandelt and
Andreas W. M. Dress. Weak hierarchies associated with similarity measures: an additive clustering technique. In BMB, Vol. 51:113166, 1989. Keywords: abstract network, clustering, from distances, from trees, phylogenetic network, phylogeny, Program WeakHierarchies, reconstruction, weak hierarchy. Note: http://dx.doi.org/10.1007/BF02458841.
Toggle abstract
"A new and apparently rather useful and natural concept in cluster analysis is studied: given a similarity measure on a set of objects, a subset is regarded as a cluster if any two objects a, b inside this subset have greater similarity than any third object outside has to at least one of a, b. These clusters then form a closure system which can be described as a hypergraph without triangles. Conversely, given such a system, one may attach some weight to each cluster and then compose a similarity measure additively, by letting the similarity of a pair be the sum of weights of the clusters containing that particular pair. The original clusters can be reconstructed from the obtained similarity measure. This clustering model is thus located between the general additive clustering model of Shepard and Arabie (1979) and the standard hierarchical model. Potential applications include fitting dendrograms with few additional nonnested clusters and simultaneous representation of some families of multiple dendrograms (in particular, twodendrogram solutions), as well as assisting the search for phylogenetic relationships by proposing a somewhat larger system of possibly relevant "family groups", from which an appropriate choice (based on additional insight or individual preferences) remains to be made. © 1989 Society for Mathematical Biology."



