Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2013 Mar 5;8(1):7.
doi: 10.1186/1748-7188-8-7.

Ultrametric networks: a new tool for phylogenetic analysis

Alberto Apostolico  1 , Matteo Comin, Andres Dress, Laxmi Parida
Affiliations

Ultrametric networks: a new tool for phylogenetic analysis

Alberto Apostolico et al. Algorithms Mol Biol. .

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.

PubMed Disclaimer

Figures

Figure 1
Figure 1
Illustrating the construction of the ultrametric network.
Figure 2
Figure 2
The creation of a new artificial vertex.
Figure 3
Figure 3
Ultrametric network of 54 individuals from different populations all over the world.Δ=0 and Δ=0. The labels represent: H = Han, G = German, T = Turk, J = Japanese, Ov = Ovambo, W = Western Pygmy, A = Australian Aboriginal, P = Papuan, B = San (Bushman), and M= Mongolian. A Rough classification is: J+H+M=East Asian, G+T= Caucasoid, A+P=Australian, B+W+Ov= Africans. Nodes filled with gray represent Caucasoid, the ones filled with blue represent Africans, bold nodes are Asians, and the remaining ones are from Australia.
Figure 4
Figure 4
Ultrametric network of 41 new world natives. A rough classification is: North America (Navajo, Zuni, Sioux) in blue, Central (Maya) in grey, South (Ticuna, Wichi, Toba, Chorote, Tehuelche), (Susque, Humahuaquen) in white.
Figure 5
Figure 5
Ultrametric network of 54 individuals from different populations all over the world (same as in Figure 3) for a few values of parameters Δ and Δ.
See this image and copyright information in PMC

References

    1. Agarwala R, Bafna V, Farach M, Narayanan B, Paterson M, Thorup M. On the approximability of numerical taxonomy: Fitting distances by tree metrics. Proceedings of the 7th Annual ACM‐SIAM Symposium on Discrete Algorithms. 1996;28(3):1073–1085.
    1. Farach M, Kannan S, Warnow T. A Robust model for finding optimal evolutionary trees. Algorithmica, special issue on Computational Biology. 1996;13:155–179.
    1. Gower J, Ross G. Minimum spanning trees and single linkage cluster analysis. Appl Stat. 1969;18:54–64. doi: 10.2307/2346439. - DOI
    1. Florek K, Lukaszewickz J, Perkal H, Steinhaus H, Zubrzycki S. Sur la Liaison et la Division des Points d’un Ensemble Fini. Colloq Matematicum. 1951;2:282–285.
    1. Edwards A, Sforza LC. Reconstruction of evolutionary trees. Phenetic Phylogenet Classif. 1964;6:67–76.