UltraNet

UltraNet constructs ultrametric networks from pairwise distance matrices to compute nearest ultrametric distance matrices under the L∞ metric for phylogenetic and classification analyses.

Key Features:

• Ultrametric focus: Targets optimization problems in phylogenetic analysis by operating on ultrametric distances within distance-based trees.
• Network construction from MSTs: Derives ultrametric networks from the collection of edges that form any minimum spanning tree of a given distance matrix.
• Nearest ultrametric via L∞: Computes the nearest ultrametric distance matrix to an arbitrary distance matrix using the L∞ distance metric realized through minimum spanning tree construction on the weighted graph.
• Optimal time complexity: Implements a construction algorithm with time complexity O(n^2) for a graph with n vertices.
• Improvement over Warshall: Reduces computation compared to classical O(n^3) approaches such as Warshall's algorithm for transitive closures.
• Relaxed networks and artificial points: Supports computation of relaxed networks and the introduction of artificial points to minimize the maximum distance between vertex pairs.
• Subdominant ultrametric networks: Generates subdominant ultrametric networks shown useful in experimental evaluations.

Scientific Applications:

• Phylogenetic classification: Applies ultrametric networks to classify taxa using distance-based and ultrametric trees.
• Approximation of additive trees: Uses ultrametric trees to approximate additive trees for classification tasks.
• Large-scale phylogenetics: Enables analyses on large datasets due to O(n^2) algorithmic efficiency.
• Evolutionary relationship analysis: Facilitates study of evolutionary relationships in contexts informed by the molecular clock concept and ultrametricity.

Methodology:

Constructs a minimum spanning tree for the weighted graph of the input distance matrix to derive ultrametric networks; computes nearest ultrametric matrices under the L∞ metric; implements an O(n^2) algorithm; and supports computing relaxed networks and introducing artificial points to minimize maximum pairwise distances, contrasted with Warshall's O(n^3) transitive-closure approach.