| |
   
Alberto Apostolico,
Matteo Comin,
Andreas W. M. Dress and
Laxmi Parida. Ultrametric networks: a new tool for phylogenetic analysis. In Algorithms for Molecular Biology, Vol. 8(7):1-10, 2013.
Keywords: abstract network, from distances, phylogenetic network, phylogeny, Program Ultranet.
Note: http://dx.doi.org/10.1186/1748-7188-8-7.
Toggle abstract
"Background: The large majority of optimization problems related to the inference of distance-based trees used in phylogenetic analysis and classification is known to be intractable. One noted exception is found within the realm of ultrametric distances. The introduction of ultrametric trees in phylogeny was inspired by a model of evolution driven by the postulate of a molecular clock, now dismissed, whereby phylogeny could be represented by a weighted tree in which the sum of the weights of the edges separating any given leaf from the root is the same for all leaves. Both, molecular clocks and rooted ultrametric trees, fell out of fashion as credible representations of evolutionary change. At the same time, ultrametric dendrograms have shown good potential for purposes of classification in so far as they have proven to provide good approximations for additive trees. Most of these approximations are still intractable, but the problem of finding the nearest ultrametric distance matrix to a given distance matrix with respect to the L∞ distance has been long known to be solvable in polynomial time, the solution being incarnated in any minimum spanning tree for the weighted graph subtending to the matrix.Results: This paper expands this subdominant ultrametric perspective by studying ultrametric networks, consisting of the collection of all edges involved in some minimum spanning tree. It is shown that, for a graph with n vertices, the construction of such a network can be carried out by a simple algorithm in optimal time O(n2) which is faster by a factor of n than the direct adaptation of the classical O(n3) paradigm by Warshall for computing the transitive closure of a graph. This algorithm, called UltraNet, will be shown to be easily adapted to compute relaxed networks and to support the introduction of artificial points to reduce the maximum distance between vertices in a pair. Finally, a few experiments will be discussed to demonstrate the applicability of subdominant ultrametric networks.Availability: http://www.dei.unipd.it/~ciompin/main/Ultranet/Ultranet.html. © 2013 Apostolico et al.; licensee BioMed Central Ltd."
|
|
| |
  
Andreas W. M. Dress,
Katharina Huber,
Jacobus Koolen and
Vincent Moulton. Compatible decompositions and block realizations of finite metrics. In EJC, Vol. 29(7):1617-1633, 2008.
Keywords: abstract network, block realization, from distances, phylogenetic network, phylogeny, realization, reconstruction.
Note: http://www.ims.nus.edu.sg/preprints/2007-21.pdf.
Toggle abstract
"Given a metric D defined on a finite set X, we define a finite collection D of metrics on X to be a compatible decomposition of D if any two distinct metrics in D are linearly independent (considered as vectors in RX × X), D = ∑d ∈ D d holds, and there exist points x, x′ ∈ X for any two distinct metrics d, d′ in D such that d (x, y) d′ (x′, y) = 0 holds for every y ∈ X. In this paper, we show that such decompositions are in one-to-one correspondence with (isomorphism classes of) block realizations of D, that is, graph realizations G of D for which G is a block graph and for which every vertex in G not labelled by X has degree at least 3 and is a cut point of G. This generalizes a fundamental result in phylogenetic combinatorics that states that a metric D defined on X can be realized by a tree if and only if there exists a compatible decomposition D of D such that all metrics d ∈ D are split metrics, and lays the foundation for a more general theory of metric decompositions that will be explored in future papers. © 2007 Elsevier Ltd. All rights reserved."
|
|
| |
 
Stefan Grünewald,
Kristoffer Forslund,
Andreas W. M. Dress and
Vincent Moulton. QNet: An agglomerative method for the construction of phylogenetic networks from weighted quartets. In MBE, Vol. 24(2):532-538, 2007.
Keywords: abstract network, circular split system, from quartets, phylogenetic network, phylogeny, Program QNet, reconstruction, software.
Note: http://mbe.oxfordjournals.org/cgi/content/abstract/24/2/532.
Toggle abstract
"We present QNet, a method for constructing split networks from weighted quartet trees. QNet can be viewed as a quartet analogue of the distance-based Neighbor-Net (NNet) method for network construction. Just as NNet, QNet works by agglomeratively computing a collection of circular weighted splits of the taxa set which is subsequently represented by a planar split network. To illustrate the applicability of QNet, we apply it to a previously published Salmonella data set. We conclude that QNet can provide a useful alternative to NNet if distance data are not available or a character-based approach is preferred. Moreover, it can be used as an aid for determining when a quartet-based tree-building method may or may not be appropriate for a given data set. QNet is freely available for download. © The Author 2006. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved."
|
|
| |
Andreas W. M. Dress and
Daniel H. Huson. Constructing splits graphs. In TCBB, Vol. 1(3):109-115, 2004.
Keywords: abstract network, circular split system, from trees, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network, visualization.
Note: http://scilib.kiev.ua/ieee/tcbb/2004/03/n3/n0109.pdf.
Toggle abstract
"Phylogenetic trees correspond one-to-one to compatible systems of splits and so splits play an important role in theoretical and computational aspects of phylogeny. Whereas any tree reconstruction method can be thought of as producing a compatible system of splits, an increasing number of phylogenetlc algorithms are available that compute split systems that are not necessarily compatible and, thus, cannot always be represented by a tree. Such methods include the split decomposition, Neighbor-Net, consensus networks, and the Z-closure method. A more general split system of this kind can be represented graphically by a so-called splits graph, which generalizes the concept of a phylogenetic tree. This paper addresses the problem of computing a splits graph for a given set of splits. We have implemented all presented algorithms in a new program called SplitsTree4. © 2004 IEEE."
|
|
| |
Katharina Huber,
Vincent Moulton,
Peter J. Lockhart and
Andreas W. M. Dress. Pruned Median Networks: A Technique for Reducing the Complexity of Median Networks. In MPE, Vol. 19(2):302-310, 2001.
Keywords: abstract network, median network, phylogenetic network, phylogeny, split.
Note: http://dx.doi.org/10.1006/mpev.2001.0935.
Toggle abstract
"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. © 2001 Academic Press."
|
|
| |
|
| |
|
| |
Andreas W. M. Dress,
Daniel H. Huson and
Vincent Moulton. Analyzing and visualizing distance data using SplitsTree. In DAM, Vol. 71(1):95-109, 1996.
Keywords: abstract network, from distances, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization.
Note: http://bibiserv.techfak.uni-bielefeld.de/splits/splits.pdf.
|
|
| |
Hans-Jürgen Bandelt and
Andreas W. M. Dress. An order theoretic framework for overlapping clustering. In DM, Vol. 136(1-3):21-37, 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 well-known criterion for n-conformity of hypergraphs as well as corresponding results due to Batbedat, dealing with the case n = 2. © 1994."
|
|
| |
|
| |
Hans-Jürgen Bandelt and
Andreas W. M. Dress. A canonical decomposition theory for metrics on a finite set. In Advances in Mathematics, Vol. 92(1):47-105, 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 split-decomposable. Tree metrics (and more generally, the sum of two tree metrics) are particular instances of totally split-decomposable metrics. Our main result confirms that every metric admits a coherent decomposition into a totally split-decomposable metric and a split-prime 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 four-point subset all three splits with block size two. © 1992."
|
|
| |
|
| |
Hans-Jürgen Bandelt and
Andreas W. M. Dress. Weak hierarchies associated with similarity measures: an additive clustering technique. In BMB, Vol. 51:113-166, 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 sub-set is regarded as a cluster if any two objects a, b inside this sub-set 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, two-dendrogram 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."
|
|
|
|
- forked on GitHub.