necom — NWK, CLUST, and MAT Toolkit

necom is a command-line toolkit for clustering, distance-matrix processing, and phylogenetic-tree manipulation.

The name is formed from its three command families — NWK, CLUST, and MAT — with vowels inserted in alphabetical order. It also echoes the Latin nexum(“tie” or “bond”), reflecting the toolkit’s focus on connections between clusters, matrix entries, and tree nodes.

Features

• Clustering (necom clust): hierarchical (NN-chain), DBSCAN, K-medoids, MCL, connected components, plus tree-building algorithms (Neighbor-Joining, UPGMA).
• Evaluation (necom eval): partition metrics (ARI, AMI, NMI, FMI, Jaccard, etc.), tree topology distances (Robinson-Foulds, KF), and branch-support replication.
• Tree cutting (necom cut): split Newick trees into flat partitions by height, K, root distance, clade size, dynamic cut, or hybrid dynamic + PAM; parameter sweeps via scan-*.
• Matrix utilities (necom mat): PHYLIP/pair format conversion, subsetting, pairwise comparison (Pearson, Spearman, cosine, Jaccard, MAE), and transformations (log, sqrt, normalize, etc.); from-vector computes pairwise scores from feature vectors.
• Tree operations (necom nwk): rerooting, pruning, renaming, subtree extraction, topology comparison, statistics, distance, and visualization (SVG, DOT, LaTeX Forest).
• Pipelines (necom pl condense): integrated workflows such as taxonomic tree condensation.
• Pipeline-friendly: reads from stdin / writes to stdout where possible, with predictable output and composable subcommands.
• Robust: Rust implementation with a zero-panic policy for malformed inputs.

Commands

• necom clust — cc, dbscan, hier, k-medoids, mcl, nj, upgma
• necom cut — simple, dynamic, hybrid, scan-simple, scan-dynamic
• necom eval — compare, partition, replicate
• necom mat — compare, format, from-vector, subset, to-pair, to-phylip, transform
• necom nwk
  • Information: stat, label, distance
  • Manipulation: order, prune, rename, replace, reroot, subtree, topo
  • Visualization: comment, indent, to-dot, to-forest, to-svg, to-tex
• necom pl — condense

Install

Current release: 0.4.1

necom requires the Rust nightly toolchain (pinned by rust-toolchain.toml for portable_simd), auto-installed by cargo on first use:

cargo install --path . --force

Quick start

After installation, the necom binary is available in your PATH:

necom --help
necom clust --help
necom cut --help
necom eval --help
necom mat --help
necom nwk --help
necom pl --help

Examples

# Hierarchical clustering from a PHYLIP distance matrix
necom clust hier tests/mat/IBPA.phy
# (((((IBPA_ECOLI,IBPA_ESCF3),A0A192CFC5_ECO25):0.0358,IBPA_ECOLI_GA):0.1467,...

# Compare two distance matrices
necom mat compare tests/mat/IBPA.phy tests/mat/IBPA.71.phy
# Method  Score
# pearson 0.935803

# Tree statistics
necom nwk stat tests/newick/catarrhini.nwk
# Type    phylogram
# nodes   19
# leaves  10
# rooted  Yes
# cherries        3
# sackin  36
# colless 8

# Cut a tree into clusters by height
necom cut simple --height 0.05 tests/newick/catarrhini.nwk
# Cercopithecus
# Colobus
# Gorilla
# ...

# Evaluate a partition against ground truth
necom eval partition result.tsv --other truth.tsv

# Condense a tree by taxonomy
necom pl condense --taxon tests/pipeline/strains.taxon.tsv \
    tests/pipeline/minhash.reroot.newick

Documentation

Extended documentation for each command is available in docs/:

• docs/clust.md — clustering algorithms
• docs/cut.md — tree cutting
• docs/eval.md — evaluation overview (partition & tree comparison)
• docs/eval-partition.md — partition evaluation deep dive
• docs/mat.md — matrix utilities
• docs/nwk.md — Newick tree operations
• docs/nwk-tex.md — LaTeX Forest tree export
• docs/pl.md — integrated pipelines
• docs/formats.md — shared file format conventions

Per-subcommand help text lives under docs/help/ and is also reachable via necom <command> <subcommand> --help. The rendered mdBook site is published at https://wang-q.github.io/necom/.

Author

Qiang Wang wang-q@outlook.com

License

MIT.

Copyright by Qiang Wang. 2024-

necom clust

Overview

The necom clust module provides a collection of clustering algorithms for sequences, genomic features, and general data. These tools are designed to handle the distance matrices, similarity networks, and feature vectors commonly encountered in bioinformatics.

Commands are divided into two categories by input data type (consistent with necom clust --help):

1. Tree: Build phylogenetic or hierarchical structures from a distance matrix (hier, nj, upgma).
2. Flat: Generate groups directly from pairwise relations, distances, or similarities (cc, dbscan, k-medoids, mcl). DBSCAN parameter scanning is available as scan-dbscan.

Flat partitions can also be derived from an existing tree using the separate necom cut command (see docs/cut.md).

Input and Output Conventions

Input by command type

• Tree-building commands (hier, nj, upgma): accept a PHYLIP distance matrix (strict or relaxed). Smaller values mean higher similarity.
• Flat clustering commands:
  • mcl and cc: accept pairwise similarities in TSV format (name1\tname2\tscore); higher is better.
  • dbscan and k-medoids: accept pairwise distances in TSV format (name1\tname2\tdist); lower is better.

Similarity matrices must be converted to distances before dbscan or k-medoids, e.g., with necom mat transform.

Output formats

Most flat-clustering commands support --format:

• cluster (default): one cluster per line, first element is the representative, remaining elements are members. Noise points in DBSCAN are emitted as single-member clusters.
• pair: one representative\tmember pair per line.

Tree-building commands always output a Newick tree.

Algorithm List

MCL (Markov Cluster Algorithm)

• Principle: Simulates random walks on a graph, alternating between “expansion” and “inflation” operations. This concentrates flow within strongly connected regions and causes flow in weakly connected regions to fade, naturally separating out modules.
• Command: necom clust mcl
• Characteristics: Graph clustering based on flow simulation.
• Use cases: Biological networks (e.g., SSN), protein family detection, module discovery.
• Advantages: Robust to noise; handles complex network structures.
• Input: Pairwise similarities .tsv (higher is better).
• Output: cluster (default) or pair format, controlled by --format.
• Defaults: --inflation 2.0, --prune 1e-5, --max-iter 100.
• Note: --max-iter must be greater than 0.

Connected Components (CC)

• Principle: A fundamental graph-theory concept that finds all sets of mutually reachable nodes. Edge weights are ignored; only connectivity matters.
• Command: necom clust cc
• Characteristics: The most basic connected component clustering.
• Use cases: Fast deduplication at very high similarity thresholds.
• Advantages: Extremely fast (linear complexity).
• Input: Pairwise relations in TSV format (name1\tname2\t[weight]); the weight column is ignored.
• Output: cluster (default) or pair format, controlled by --format.

K-Medoids

• Principle: Iterative optimization similar to K-Means, but the center (medoid) must be an actual sample from the dataset. Centers are updated by minimizing the sum of dissimilarities to the nearest center.
• Command: necom clust k-medoids (alias km)
• Characteristics: Like K-Means, but centers must be actual samples (medoids).
• Use cases: Noise-resistant scenarios, or when only a distance matrix (non-Euclidean space) is available.
• Advantages: Robust to outliers; interpretable results because centers are real samples.
• Input: Pairwise distances .tsv (lower is better).
• Output: cluster (default) or pair format, controlled by --format.
• Defaults: --runs 10, --max-iter 100.
• Note: --k must not exceed the number of samples.
• Note: If a cluster becomes empty during iteration, it is omitted from the output, so the final number of clusters may be less than k.

DBSCAN

• Principle: Density-based clustering. Starting from any point, if the number of points within its $\epsilon$ neighborhood exceeds min_points, it becomes a core point and expands a cluster; regions with insufficient density are treated as noise.
• Command: necom clust dbscan
• Characteristics: Density-based clustering that requires specifying neighborhood radius eps and minimum point count min_points.
• Use cases: Non-convex cluster shapes, uneven density distributions, outlier detection.
• Advantages: Does not require specifying the number of clusters K; identifies noise.
• Input: Pairwise distances .tsv (lower is better).
• Output: cluster (one cluster per line, first element is the representative) or pair (representative–member pairs). Noise points are emitted as single-member clusters.
• Defaults: --eps 0.05, --min-points 4.
• Note on --min-points: By default (--same 0.0), the neighborhood count includes the point itself because self-distance is 0 and is always <= eps. If --same is set to a value greater than eps, the point is not counted as its own neighbor and may fail to become a core point.
• Representative selection: By default (--rep medoid), the representative of each cluster is its medoid (the point with the smallest average distance to other cluster members). Use --rep first to use the first-discovered point instead. Noise points are emitted as single-member clusters where the representative is the point itself.
• --min-pct: Alternative to --min-points; specify min_points as a fraction of the total number of samples. The effective value is ceil(P * n_samples), range (0, 1]. Mutually exclusive with --min-points.
• Parameter scanning: To scan eps and compare internal metrics, use necom clust scan-dbscan (see below).

DBSCAN Scan (scan-dbscan)

• Principle: Run DBSCAN repeatedly over a range of eps values while keeping min_points fixed. For each eps, report the number of clusters, the number of noise points, and two internal validity indices (Silhouette and Davies-Bouldin). Optionally, select the best eps according to a criterion and output the corresponding partition.
• Command: necom clust scan-dbscan
• Characteristics: Parameter exploration for DBSCAN without ground truth.
• Use cases: Choose an appropriate eps when the distance scale of the data is unknown.
• Input: Pairwise distances .tsv (lower is better).
• Output:
  • Without --opt-eps: a TSV table with columns Epsilon, Clusters, Noise, Silhouette, DBIndex.
  • With --opt-eps: a clustering partition in cluster or pair format, using the same conventions as necom clust dbscan.
• Required: --scan <start,end,step>.
• Options:
  • --min-points <N> or --min-pct <P>: same semantics as necom clust dbscan.
  • --opt-eps {silhouette|max-clusters|min-noise}: select the best eps and output its partition.
    • silhouette: maximize Silhouette score.
    • max-clusters: maximize the number of non-noise clusters.
    • min-noise: minimize the number of noise points.
    • Ties are resolved by choosing the smaller eps.
• Metrics: Silhouette and Davies-Bouldin use the distance-matrix definitions described in docs/eval-partition.md. Noise points are treated as singleton clusters when computing metrics.
• Performance: Scanning costs steps × O(N²); reduce the range or step count for large matrices.
• Note: The explicit end value of --scan is always included, even if the step size does not divide the interval evenly.

UPGMA

• Principle: Unweighted Pair Group Method with Arithmetic Mean. A bottom-up hierarchical clustering that repeatedly merges the two closest clusters; distances between the new cluster and all others are computed as arithmetic averages of all member-to-member distances. Assumes a constant evolutionary rate (molecular clock).
• Command: necom clust upgma
• Characteristics: Hierarchical clustering (average linkage) that outputs a rooted tree.
• Use cases: Phylogenetic analysis assuming a molecular clock (ultrametric).
• Advantages: Produces a hierarchical structure with branch heights carrying clear distance meaning.
• Input: PHYLIP distance matrix (strict or relaxed).
• Output: Newick tree.
• Note: For input that violates the ultrametric assumption, branch lengths are clamped to 0 so the output remains a valid Newick tree.

NJ (Neighbor-Joining)

• Principle: Neighbor-Joining. Iteratively merges the pair of nodes with the smallest net divergence by minimizing total tree length (based on the Q-matrix-corrected distances). Does not assume a molecular clock and allows different evolutionary rates across branches.
• Command: necom clust nj
• Characteristics: Distance-matrix tree-building algorithm that outputs a Newick tree rooted at the midpoint of the final edge.
• Use cases: General additive distances (no molecular-clock assumption); evolutionary tree construction.
• Advantages: Fast; robust to different evolutionary rates.
• Input: PHYLIP distance matrix (strict or relaxed).
• Output: Newick tree rooted at the midpoint of the final edge.
• Note: For non-additive distances, negative branch lengths are clamped to 0 so the output remains a valid Newick tree.

Hierarchical Clustering

• Principle: A general bottom-up (agglomerative) clustering framework. Clusters are merged according to different linkage criteria (e.g., Ward minimum variance, Complete maximum distance), building a complete dendrogram hierarchy.
• Command: necom clust hier (alias hclust)
• Characteristics: General hierarchical clustering supporting single, complete, average, weighted, centroid, median, ward.
• Default method: ward (use --method to select other linkage criteria).
• Implementation status: Implemented with $O(N^2)$ NN-chain optimization for reducible methods (single, complete, average, weighted, ward); centroid and median fall back to the primitive $O(N^3)$ implementation because they do not satisfy the reducibility property.
• Use cases: General hierarchical clustering analysis; combined with necom cut for flexible groupings at different granularities.
• Advantages: Supports multiple linkage methods; the default NN-chain implementation achieves $O(N^2)$ time for reducible methods.
• Input: PHYLIP distance matrix (strict or relaxed).
• Output: Newick tree.
• Details: Hierarchical Clustering Details

Hierarchical Clustering Details

necom clust hier (alias hclust) provides general hierarchical clustering (dendrogram) generation, supporting single, complete, average, weighted, centroid, median, and ward methods, outputting Newick format for downstream necom cut.

Background and Positioning

• Module: clust, alongside k-medoids, mcl, etc.
• Goal: Statistically meaningful dendrograms (merge heights express the cost of the linkage criterion), without enforcing “evolution/molecular-clock” semantics.
• Synergy with existing necom capabilities:
  • Tree building: clust upgma (rooted, ultrametric) and clust nj (additive, rooted at the midpoint of the final edge) already exist.
  • Cutting: tree-cut grouping via necom cut.
  • Evaluation: necom eval partition --matrix / --tree / --coords (currently available); necom eval tree not yet implemented.

Relationship to UPGMA/NJ

• Commonalities: All take a distance matrix as input and output a tree-like structure; all can be combined with necom cut to obtain flat groupings.
• Relationship to UPGMA:
  • R hclust(method="average") is equivalent to “average linkage”; UPGMA is a specialized version under the “ultrametric (molecular clock)” assumption, producing a rooted, strictly ultrametric tree whose branch lengths have “time/evolution” meaning.
  • Conclusion: The linkage updates are identical, but the semantics differ; UPGMA leans toward phylogenetic scenarios, while clust hier leans toward statistical clustering.
• Relationship to NJ:
  • NJ (Neighbor-Joining) minimizes total tree length via the Q matrix, producing an “additive minimum-length tree” that does not belong to the linkage-update paradigm and outputs a Newick tree rooted at the midpoint of the final edge.
  • For general additive distances, NJ is more robust than UPGMA; if the distances are ultrametric, UPGMA/hclust-average and NJ usually agree topologically (unrooted view).

Methods and Algorithm Essentials

• single/complete/average: Standard linkage updates (Lance–Williams framework); merge height is the distance/cost corresponding to the linkage criterion.
• ward:
  • Concept: Minimizes the increase in within-cluster sum of squares (total within-group variance, SSE); commonly used and robust.
  • Update (squared-distance version, where n is cluster size):
    • Let the squared distance between merged cluster u∪v and a third cluster k be:
    • d(u∪v,k)^2 = [ (n_u+n_k) d(u,k)^2 + (n_v+n_k) d(v,k)^2 − n_k d(u,v)^2 ] / (n_u+n_v+n_k)
  • If the input is non-squared distances: square them for the update, and take the square root or use the SSE-increment definition for merge heights when outputting.
  • Distance prerequisite: Theoretically requires Euclidean or near-Euclidean distances; usable on general biological distances, but the statistical interpretation of “variance minimization” becomes weaker.

Output and Conventions

• Outputs Newick dendrogram:
  • Merges are emitted in the order they are performed by the linkage algorithm (merge-order output). The internal node IDs increase with the merge sequence, matching the convention used by R hclust and SciPy linkage.
  • Internal node height is half the merge distance (height = distance / 2), and branch length from child to parent is parent_height - child_height.
  • For reducible methods (single/complete/average/weighted/ward), the output is ultrametric-like: all leaves under the same internal node have equal total distance to that node. centroid/median may violate this property due to non-monotonic merge heights (inversions), even after negative branch lengths are clamped to zero.
  • Branch lengths express merge heights (linkage cost or SSE increment with appropriate unit handling).
  • Strict ultrametricity is not guaranteed (unless the data satisfy the corresponding conditions), but the output satisfies the requirements of necom cut simple --height <H>.
• Numeric format: branch lengths are emitted with Rust’s default float formatting. For a fixed-width, six-decimal view consistent with necom nwk distance, post-process the tree or use necom nwk distance on the resulting branch lengths.

Notes

• clust hier only accepts distance matrices (smaller values mean higher similarity). Similarity matrices must be converted first, e.g., with necom mat transform.
• ward, centroid, and median updates use squared distances internally; output branch lengths are expressed in the original distance units, so you do not need to square the input.
• ward theoretically assumes Euclidean or near-Euclidean distances; on general biological distances the statistical interpretation of “minimum variance” is weaker.
• centroid and median linkage may produce non-monotonic merge heights (inversions); this is an algorithmic characteristic of these methods.
• For reducible methods (single, complete, average, weighted, ward), the default NN-chain implementation produces the same dendrogram as the primitive $O(N^3)$ algorithm, but the concrete merge order may differ. Consequently, the Newick string may have a different internal node ordering than clust upgma for the same method, even though the underlying clustering is equivalent.
• Ties in nearest-neighbor selection are broken deterministically by cluster index; because hier operates on the indexed distance matrix, this is independent of sample name alphabetical order.

Recommended Hier Workflow

• Generate tree:
  • Near-molecular-clock/ultrametric scenarios: clust upgma outputs a rooted ultrametric tree.
  • General additive-distance scenarios: clust nj.
  • General hierarchical analysis or when ward is needed: clust hier --method ward.
• Cut and evaluate:
  • Cut: necom cut simple tree.nwk --height H or TreeCluster-style thresholds/constraints.
  • Internal evaluation (no Ground Truth): necom eval partition --matrix ... (Silhouette) (currently available); necom eval tree not yet implemented.
  • External evaluation (with Ground Truth): necom eval partition (ARI/AMI/V-Measure).

Evaluation

Partition evaluation has moved to necom eval partition. See docs/eval.md for the overview and docs/eval-partition.md for detailed metric definitions.

Implementation Status

Algorithm Selection Guide

Choosing the right clustering command depends on the input data and the biological or analytical question.

• Need a tree from a distance matrix?
  • necom clust upgma — when the data are expected to be ultrametric (molecular clock).
  • necom clust nj — for general additive distances without a molecular-clock assumption.
  • necom clust hier --method ward — for statistical hierarchical clustering with flexible linkage criteria.
• Need flat groups from pairwise similarities?
  • necom clust mcl — biological networks and protein families.
  • necom clust cc — fast deduplication when connectivity alone matters.
• Need flat groups from pairwise distances?
  • necom clust k-medoids — when centers must be actual samples or the metric is non-Euclidean.
  • necom clust dbscan — for non-convex shapes, uneven densities, or outlier detection.
• Have feature vectors?
  • Use necom eval partition --coords (via necom eval) for geometry-based validation, or wait for the planned necom clust gmm command.

Why Some Common Algorithms Are Not Provided

The following classic algorithms are intentionally not included in necom clust. They have clear limitations for the biological sequence and network scales this project targets, and a better alternative already exists or is planned.

• K-Means: Assumes spherical, equal-variance clusters and centroids that are not real samples. Use necom clust k-medoids instead.
• Bisecting K-Means: Inherits K-Means limitations and favors divisive splitting. Use necom clust hier or necom clust upgma for bottom-up trees.
• Affinity Propagation: $O(N^2)$ cost makes it impractical for > 10k sequences. Use necom clust k-medoids for small representative sets, or necom clust dbscan / necom clust mcl for automatic cluster counts.
• Spectral Clustering: Building the Laplacian and eigendecomposition is expensive ($O(N^3)$). Use necom clust mcl on biological networks for similar results with better scalability.
• Mean Shift: High complexity and sensitive bandwidth selection. Use necom clust dbscan or the planned necom clust gmm.
• OPTICS: Its core idea is better automated by HDBSCAN. Use the planned necom clust hdbscan.
• Biclustering: Designed for gene-expression matrix sub-blocks, not sample grouping. Use specialized tools such as WGCNA when needed.
• BIRCH: Relies on Euclidean statistics and restricts cluster shapes. Use external vector tools for large-scale vectors, or necom clust mcl for large networks.

Planned

GMM, HDBSCAN, Louvain/Leiden and other algorithms are on the roadmap. Detailed implementation analysis and algorithms considered but not adopted are documented in notes/design/clust-impl.md.

Bootstrap Support for Hierarchical Clustering [Moved to necom eval]

necom eval boot will compute multiscale-bootstrap BP/AU/SI support values (pvclust-style) for each internal node of a hierarchical clustering tree, quantifying the stability of clusters under feature resampling. Design details are in notes/design/eval-boot.md.

GMM (Gaussian Mixture Models) [Planned]

Motivation for introducing GMM:

• Soft Clustering: Unlike the hard assignment of K-means, GMM gives the probability that a sample belongs to each cluster, suitable for fuzzy biological classifications (e.g., subspecies, gene-family transitional states).
• Non-spherical clusters: Models different shapes and sizes through covariance matrices (K-means assumes equal-variance spherical clusters).
• Generative model: Can be used for density estimation and outlier detection.

Planned interface:

# GMM clustering from CSV/TSV vector input
necom clust gmm input.tsv --k 5 --cov full > clusters.tsv

# Output includes: ID, Cluster, PosteriorProb

Model Selection

How to determine the number of clusters (K) or the best model complexity?

• BIC (Bayesian Information Criterion) [Planned]:
  • In GMM, BIC trades off log-likelihood (goodness of fit) against the number of parameters (complexity).
  • necom could provide clust gmm --scan-k 2..20, automatically computing and outputting a BIC curve to help users choose the best K (usually the BIC minimum or elbow).
• Silhouette / Calinski-Harabasz [Partially supported]: Geometry-based evaluation metrics suitable for K-means or general distance clustering (eval partition already supports distance-matrix Silhouette; tree-based Silhouette is planned for necom eval tree [Planned]).

Large-Scale Data Strategy

For large-scale data with $N > 20,000$, the memory ($O(N^2)$) and computation ($O(N^2)$) costs of fully connected hierarchical clustering increase sharply.

Memory estimate (f32 condensed matrix):

• 1 GiB: ~23,000 points
• 10 GiB: ~73,000 points
• 32 GiB: ~130,000 points
• 64 GiB: ~185,000 points

Implications: Even on a high-end server with 64 GiB memory, processing $N=200k$ is near the limit.

Recommended strategy: Use a “two-step” approach combining fast clustering with careful tree building.

1. Pre-clustering/compression: Use linear or near-linear algorithms (e.g., necom clust k-medoids, necom clust mcl, or external tools such as mmseqs2) to compress data into $K$ representative points ($K \approx 5000 \sim 10000$).
2. Hierarchical clustering: Extract the distance matrix among representative points and run necom clust hier to build the backbone tree.

Workflow example:

# 1. Fast clustering to select representatives (k=5000)
necom clust k-medoids all_distances.tsv --k 5000 --format pair > clusters.tsv

# 2. Extract representative list (Unix `cut`, not `necom cut`)
cut -f1 clusters.tsv | sort -u > representatives.list

# 3. Extract sub-matrix for representatives
necom mat subset all_distances.phy representatives.list -o sub_matrix.phy

# 4. Build tree on representatives
necom clust hier sub_matrix.phy --method ward > backbone.nwk

Recommended Workflows

Scenario A: Protein Family Mining (Graph-based)

# 1. Build sequence-alignment network (e.g., mmseqs/blast -> pair.tsv)
# 2. MCL clustering
necom clust mcl pairs.tsv --inflation 2.0 > families.tsv

Scenario B: Hierarchical Clustering Parameter Scanning and Evaluation Workflow

Combine necom cut scanning with eval partition batch evaluation to find the best cutting threshold.

# 1. Generate hierarchical clustering tree
necom clust hier matrix.phy --method ward > tree.nwk

# 2. Scan thresholds, save to a file, and evaluate internal metrics (Silhouette)
# necom cut scan-simple outputs a long table; write it to a file for eval partition
necom cut scan-simple tree.nwk --height --range 0,1.0,0.05 > partitions.tsv
necom eval partition partitions.tsv --input-format long --matrix matrix.phy > evaluation.tsv

# 3. Analyze evaluation.tsv to choose the best threshold (e.g., maximum Silhouette)
# Assume the best threshold is 0.45
necom cut simple tree.nwk --height 0.45 > final_clusters.tsv

For input/output format conventions used by necom clust and other commands, see docs/formats.md.

necom cut

necom cut cuts a Newick tree (phylogenetic or hierarchical clustering tree) into flat clustering partitions.

Unlike necom clust (which builds clusters from data), cut focuses on “deriving groups from an existing tree structure.” It supports multiple biological and statistical cutting rules and provides stable, reusable tabular output.

This document describes the command’s algorithm patterns, parameter-selection guidelines, and input/output conventions.

Subcommand Overview

necom cut is organized into five focused subcommands:

• necom cut simple: static threshold methods such as k, height, max-clade, avg-clade, and inconsistent.
• necom cut dynamic: Dynamic Tree Cut (top-down adaptive, --min-size).
• necom cut hybrid: Dynamic Hybrid Cut (tree + distance matrix, --min-size, --matrix).
• necom cut scan-simple: parameter sweep over a static method threshold.
• necom cut scan-dynamic: parameter sweep over dynamic-tree min cluster sizes.

Run necom cut <subcommand> --help for the full option list of each subcommand.

Relationship to Clustering Algorithms

The necom cut command works with trees generated by clustering algorithms like necom clust hier, necom clust upgma, necom clust nj, or external tools. It transforms hierarchical tree structures into flat partitions, complementing the clustering workflow by providing flexible grouping at different granularities. The resulting partitions can be evaluated with necom eval partition.

Use Cases and Design Rationale

In practice, we often already have a tree (phylogenetic or hierarchical clustering tree) and want to cut its leaves into different groups (partitions) at some threshold. Cutting rules can vary: by height, by number of clusters, by maximum within-cluster distance (diameter), requiring monophyly (clade), etc.

necom cut aims to provide a comprehensive, efficient, and standardized cutting toolkit:

• Algorithm core: Implements basic cuts by cluster count and height, with logic consistent with SciPy.cluster.hierarchy and R cutree; it also fully ports TreeCluster’s biological-constraint algorithms (e.g., max-clade, med-clade), optimized for phylogenetic trees.
• Performance and usability improvements:
  • High performance: Rust-based implementation with no Python/R runtime dependencies, handling large trees more efficiently.
  • Standardized: Unifies terminology differences across source algorithms (e.g., consistently using height, max-edge), reducing cognitive load.
  • Composable: As part of the necom toolchain, it can directly cooperate with eval partition for clustering evaluation.

Supported Modes and Algorithms

necom cut provides a rich set of cutting algorithms, ranging from simple threshold cuts to complex biologically constrained clustering. Detailed definitions and complexity analyses are given below. All static methods are invoked through necom cut simple <infile> --<METHOD> <T>.

1. Cut by Cluster Count (--k)

• Definition: Split the tree into $K$ clusters produced by $K-1$ cuts. Cutting order is based on node height (distance to the farthest leaf), prioritizing nodes with the largest height.
• Complexity: $O(N \log N)$, where $N$ is the number of leaves. Requires sorting all internal nodes by height.
• Use case: Exploratory analysis when you only want a fixed number of groups and do not care about the exact distance threshold.

2. Cut by Height (--height)

• Definition: Cut all edges whose node height (distance to the farthest leaf) is greater than $H$.
  • For any resulting cluster $C$, all nodes $u$ in it satisfy $height(u) \le H$.
  • Equivalent to SciPy’s fcluster(criterion='distance') or R’s cutree(h=H).
• Complexity: $O(N)$. Only one post-order traversal is needed.
• Use case: Suitable for ultrametric trees, where height strictly represents time or genetic distance.

3. Cut by Root Distance (--root-dist)

• Definition: Cut all edges whose path length from the root exceeds $D$.
  • For the root node $r_C$ of any resulting cluster $C$ formed by a cut, $dist(root, r_C) > D$.
  • Once a path’s cumulative length exceeds $D$, that path is cut and no longer extends downward.
• Complexity: $O(N)$. Only one pre-order traversal is needed.
• Use case: Phylogenetic analysis defining clades that diverged a certain time after the common ancestor (root).

4. Cut by Maximum Within-Cluster Diameter (--max-clade)

• Definition: Partition leaves into non-overlapping clusters $C_1, C_2, \ldots, C_m$. For each $C_i$:
  1. Monophyly: Leaves in $C_i$ must form a clade in the original tree $T$.
  2. Diameter constraint: $\max_{u, v \in C_i} dist(u, v) \le T$.
  3. Support constraint (if --support is specified): The path between any two points in $C_i$ must not contain edges with support below the threshold.
• Algorithm: TreeCluster “Max Clade” algorithm. Uses efficient bottom-up diameter computation and top-down greedy selection.
• Complexity: $O(N)$ for binary trees, $O(N \log N)$ worst-case for highly multifurcating trees (sorting children depths at each internal node). Avoids the $O(N^2)$ all-pairs distance computation.
• Use case: Virus subtyping, OTU clustering, and other scenarios requiring strict control of within-cluster divergence.

5. Cut by Average Within-Cluster Distance (--avg-clade)

• Definition: Similar to max-clade, but the constraint is:
  1. Monophyly.
  2. Average distance constraint: $\frac{1}{|C_i|(|C_i|-1)} \sum_{u, v \in C_i, u \neq v} dist(u, v) \le T$.
  3. Support constraint.
• Algorithm: TreeCluster “Avg Clade” algorithm. Maintains within-subtree distance sums and node counts bottom-up.
• Complexity: $O(N)$.
• Use case: Compared to maximum distance, average distance is more robust to individual outliers.

6. Cut by Median Within-Cluster Distance (--med-clade)

• Definition: Similar to max-clade, but the constraint is:
  1. Monophyly.
  2. Median distance constraint: $median({dist(u, v) \mid u, v \in C_i, u \neq v}) \le T$.
  3. Support constraint.
• Algorithm: TreeCluster “Med Clade” algorithm. Computes medians by sorting the pairwise distance list at each internal node bottom-up.
• Complexity: $O(N^2 \log N)$ on balanced trees; degrades to $O(N^3 \log N)$ on degenerate (comb) trees, because each level re-sorts an $O(L^2)$ list of pairwise distances where $L$ is the subtree leaf count. Significantly more expensive than the previous two methods.
• Note: Not recommended for very large trees (e.g., > 10k leaves) unless median robustness is truly required.

7. Cut by Total Within-Cluster Branch Length (--sum-branch)

• Definition: Similar to max-clade, but the constraint is:
  1. Monophyly.
  2. Total branch length constraint: The total branch length of the minimal subtree spanning cluster $C_i$ (Phylogenetic Diversity, PD) $\le T$.
  3. Support constraint.
• Biological meaning: Total branch length corresponds to Phylogenetic Diversity (PD), representing the total evolutionary history contained in the cluster.
• Algorithm: TreeCluster “Sum Branch Clade” algorithm.
• Complexity: $O(N)$.
• Notes:
  • PD is an extensive quantity (monotonically increasing with sample size), unlike diameter or average distance, which are “intensive quantities.”
  • Therefore, as a cutting threshold it tends to chop tight large clusters (because accumulated branch length easily exceeds the limit) while retaining loose small clusters.
  • Unless there is a specific biological reason (e.g., “limit the maximum evolutionary potential of each OTU”), it is generally not recommended as the primary cutting criterion.

8. Cut by Leaf Distance (--leaf-dist-max/min/avg)

• Definition: Cutting based on the distance from the cluster root to leaves.
  • Max Leaf Dist (--leaf-dist-max): Cut the tree so that the maximum distance from the cluster root to any leaf is $\le T$.
    • Equivalent to root_dist(max_depth - T).
    • Similar to height, but suitable for non-ultrametric trees, aligned by the farthest leaf.
  • Min Leaf Dist (--leaf-dist-min): Cut the tree so that the minimum distance from the cluster root to any leaf is $\le T$.
    • Equivalent to root_dist(min_depth - T).
  • Avg Leaf Dist (--leaf-dist-avg): Cut the tree so that the average distance from the cluster root to all leaves is $\le T$.
    • Equivalent to root_dist(avg_depth - T).
• Complexity: $O(N)$. Requires a prior traversal to compute depth statistics.
• Use case: Non-ultrametric trees (e.g., virus trees), where “time” is not uniform and one needs to look back from sampling times (leaves).

9. Cut by Maximum Edge Length (--max-edge)

• Definition: Cut all edges whose length is greater than $T$.
  • For any resulting cluster $C$, all edges $e$ in it satisfy $length(e) \le T$.
  • This method is also known in graph theory as Single Linkage Clustering: as long as two points are connected by a path of “short edges” ($\le T$), they belong to the same cluster. --single-linkage is exposed as an alias of --max-edge.
• Complexity: $O(N)$. Only one traversal is needed.
• Use cases:
  • Remove the influence of long branch attraction.
  • Quickly identify tightly connected groups while ignoring sparse connections.

10. Cut by Inconsistency Coefficient (--inconsistent)

• Definition: Cut based on the “inconsistency” of a node relative to its subtrees.
  • For each non-leaf node $i$, compute its inconsistency coefficient $I_i = \frac{h_i - \mu}{\sigma}$, where $H$ is the set of all merge heights within $d$ levels (--deep) below node $i$, $h_i$ is the height of node $i$, and $\mu$, $\sigma$ are the mean and standard deviation of $H$.
  • SciPy reference: scipy.cluster.hierarchy.inconsistent.
  • Traverse from the root downward for each node $i$:
    • Compute the maximum inconsistency coefficient $M_i$ in the subtree rooted at $i$.
    • If $M_i \le T$, the subtree is sufficiently “consistent”; treat $i$ and its leaves as one cluster and stop splitting.
    • If $M_i > T$, the subtree contains significantly inconsistent merge points; continue checking $i$’s children.
  • Leaf nodes naturally form a cluster.
• Complexity: $O(N)$.
• Use case: When overall evolutionary rates are uneven, find “natural” cluster boundaries.

11. Dynamic Tree Cut (necom cut dynamic)

• Definition: Based on the cutreeDynamicTree algorithm in the R package dynamicTreeCut (dynamicTreeCut/R/cutreeDynamic.R).
• Principle: Top-down recursive algorithm.
  1. First perform an initial cut based on global height.
  2. For each preliminary cluster, analyze its internal structure (height distribution).
  3. If a cluster contains significant substructure (i.e., a split point satisfying conditions for “height difference” and “subcluster size”), recursively split it further.
• Options:
  • --min-size <N>: Minimum cluster size (required).
  • --deep-split: Enable more aggressive splitting (corresponds to deepSplit=TRUE in R).
  • --max-tree-height <H> (optional): Maximum merge height (default 99% tree height).
• Input: Only the tree structure (dendrogram) is needed; no distance matrix is required.
• Use cases:
  • Only tree structure is available; fast, automated cutting is desired.
  • Suitable for nested structures with small clusters inside large clusters.

12. Hybrid Dynamic Cut (necom cut hybrid)

• Definition: Based on the cutreeHybrid algorithm in the R package dynamicTreeCut.
• Principle: Two-phase bottom-up algorithm.
  1. Core Detection:
     • Implements the bottom-up algorithm of R cutreeHybrid, identifying “core clusters” that satisfy tightness (Core Scatter) and separation (Gap) requirements.
  2. PAM-like Reassignment: Uses the original distance matrix to adsorb objects left unassigned in the first phase (outliers/singletons) to the nearest core cluster (medoid-based assignment).
     • Default behavior is consistent with R (pamStage=TRUE, pamRespectsDendro=TRUE, respectSmallClusters=TRUE).
• Input: Requires both tree structure and the original distance matrix (--matrix).
• Options:
  • --min-size <N>: Minimum cluster size (required).
  • --matrix <FILE>: Distance matrix file (PHYLIP format).
  • --max-pam-dist <D>: Maximum distance threshold for PAM assignment (default equals the cut height cutHeight). If an unassigned point’s distance to the nearest medoid exceeds this value, it remains unassigned.
  • --no-pam-dendro: Disable the dendrogram constraint in the PAM stage (allows assigning objects across high branches). By default the PAM stage respects tree structure (pamRespectsDendro=TRUE).
  • --max-tree-height <H> (optional): Maximum joining height. Default is ref_height + 0.99 * (max_height - ref_height), where ref_height is the 5th percentile of merge heights and max_height is the maximum merge height. Unlike cut dynamic (which uses 0.99 * root_height), this formula anchors the cut to the 5th percentile so that a few extreme merges do not inflate the threshold.
• Use cases:
  • High accuracy at cluster boundaries is required.
  • The distance matrix is needed to correct small errors or uncertainties in the tree structure.
  • Can effectively identify and handle outliers.

13. Support Filtering (--support <S>)

• Definition: A preprocessing step for all the above methods.
  • Traverse all edges in the tree; if an edge’s support value $< S$, its length is set to a very large finite sentinel (effectively $+\infty$), forcing any clustering that crosses it to exceed the cut threshold.
  • Default behavior: For nodes without explicit support values (e.g., internal nodes produced by parsing multifurcating trees), necom defaults their support to 100 (fully trusted).
• Effect: Any clustering attempt that crosses a low-support edge will fail because the distance/height exceeds the limit, thereby forcing a cut at low-support positions.

Input and Output

Input

• Input tree: Newick format (single tree).
• Branch lengths: Used for distance/height-related methods (e.g., root distance, max pairwise distance).
• Branch support (optional): If nodes/edges carry support values (e.g., bootstrap), they can be used as a “non-crossable” constraint.

Output

Output follows the same conventions as necom clust dbscan for interoperability with existing tools:

• cluster format: Each line contains all points of one cluster; the first point is the representative.
• pair format: Each line contains a pair (representative, cluster member).
  • Representative: the representative point of the cluster.
  • Member: a cluster member.
  • Singleton: the representative is itself.

Representative selection (--rep): Applies to both cluster and pair formats:

• root (default): the member closest to the root (alphabetical order as tie-break).
• medoid: Medoid, i.e., the member with the smallest sum of distances to other members.
• first: the alphabetically first member.

Common Options

• --format {cluster|pair}: Output format. Default: cluster. Used by simple, dynamic, and hybrid.
• --rep {root|medoid|first}: Representative selection. Default: root.
• --deep <N>: Depth used by the inconsistent method. Default: 2.
• --support <S>: Treat edges with support < S as effectively infinite length, forcing a cut. Default behavior treats unlabeled internal nodes as support 100.0.

Workflow and Toolchain Collaboration

To keep commands focused and orthogonal, we recommend the following “generate-evaluate” separated workflow:

1. Generate

Use necom cut:

• It only “cuts”; it does not “evaluate.”
• Supports multiple strategies (simple, dynamic, hybrid) and parameter scanning (scan-simple, scan-dynamic).
• Outputs standard TSV format.

2. Evaluate

Evaluating clustering quality usually requires a reference standard (Ground Truth) or comparison with other results. This logic is placed in separate necom eval commands; tree-topology comparison is also available via necom eval compare:

• General metrics (necom eval partition, necom mat compare):
  • Input: two clustering result TSVs (or one result + one reference); or two distance matrices for Cophenetic correlation.
  • Output: ARI (Adjusted Rand Index), AMI (Adjusted Mutual Information), V-Measure, etc.; or matrix similarity scores from mat compare.
  • Use case: When the true classification of samples is known, or when you want to compare the difference between two cutting parameters.
• Tree-related metrics (necom eval tree [planned]):
  • Input: tree file + clustering result.
  • Output: Silhouette score (based on tree distance matrix), tree geometry metrics, etc.
  • Use case: No true classification is available; assess compactness or separability of clusters on the tree structure.

Recommended Workflow Examples

1. Classic Phylogenetic Analysis

# 1. Scan different parameters to generate multiple clustering results
# necom cut scan-simple input.nwk --max-clade --range 0.01,0.10,0.01 > partitions.tsv

# 2. Select the best threshold and generate final clusters
necom cut simple input.nwk --max-clade 0.05 > final_cluster.tsv

# 3. Extract the subtree corresponding to the first cluster in final_cluster.tsv
head -1 final_cluster.tsv | tr '\t' '\n' > cluster1.names
necom nwk subtree input.nwk -l cluster1.names > cluster1.nwk

2. Hierarchical Clustering (hclust) Integration

Starting from a distance matrix, generate a tree with necom clust hier, cut it, and evaluate. A complete worked example (hier → cut scan-simple → eval partition) is in docs/clust.md.

3. SciPy-style Analysis (Inconsistency Coefficient)

For trees with uneven evolutionary rates, the inconsistency coefficient can find more natural cluster boundaries.

# Cut using inconsistency coefficient (default depth=2)
necom cut simple tree.nwk --inconsistent 1.5 > clusters.tsv

Choosing Threshold / Cluster Count: Scanning and Criteria

In cut scenarios, users commonly make two types of choices:

• Directly specify the cluster count K (analogous to R cutree(k=...)).
• Specify a threshold t (distance/height/diameter etc.) and let the threshold determine the cluster count.

When unsure about K or t, use scan-simple or scan-dynamic for parameter scanning.

Scanning

necom provides explicit scanning capability through necom cut scan-simple and necom cut scan-dynamic.

Usage: necom cut scan-simple tree.nwk --<NAME> --range <start>,<end>,<step> (Note: scanning only targets the main threshold parameter of the method. For inconsistent, it scans the coefficient threshold T, while depth --deep remains fixed at the user-specified or default value.)

• Non-Singletons: The metric that TreeCluster argmax_clusters tries to maximize.
• MaxSize: Helps judge whether a “super-cluster” exists (under-clustering).

Output Format in Scan Mode

Scan subcommands always emit long format:

1. Standard output (stdout): Always outputs a detailed partition table (Long format / Tidy Data).
   • Column definitions: Group, ClusterID, SampleID.
   • The Group column is formatted as Method=Value (e.g., height=0.5, max-clade=0.02), making it easy to distinguish different cutting parameters.
   • This format can be directly used as input for necom eval partition --input-format long for batch evaluation.
2. Statistics output (--stats-out): If specified, writes the summary statistics table (threshold, cluster count, singleton count, non-singleton count, max cluster size) to that file.

Example:

# 1. Output only the detailed partition table (for downstream analysis or evaluation)
necom cut scan-simple tree.nwk --max-clade --range 0,0.5,0.01 > partitions.tsv

# 2. Save statistics at the same time (for quick inspection)
necom cut scan-simple tree.nwk --max-clade --range 0,0.5,0.01 --stats-out stats.tsv > partitions.tsv

Integration with necom eval partition

necom cut and necom eval partition work together through the Long format, supporting two evaluation modes:

• Batch internal evaluation: pipe scan output to necom eval partition --input-format long with --matrix, --tree, or --coords to score every threshold without Ground Truth.
• Targeted external evaluation: first use scan-simple to locate promising threshold ranges, then generate partitions for selected thresholds and compare them to Ground Truth with necom eval partition --other.

Concrete command examples are kept in docs/clust.md to avoid duplication.

Threshold-Selection Strategy Reference

When unsure about the best threshold, use scan-simple or scan-dynamic to generate data and refer to the following common strategies for decision-making:

Strategy 1: Maximize Non-Singleton Clusters

• Principle: Find a threshold that maximizes the number of “non-singleton clusters” (clusters with > 1 member).
• Applicability: When you expect as many meaningful (> 1 member) clusters as possible while avoiding over-chopping (many singletons) or under-cutting (huge clusters).
• Operation: Observe the Non-Singletons column in the scan result table and choose the threshold corresponding to its maximum.

Strategy 2: Elbow Rule

This is a general strategy in data analysis.

• Principle: Look at the curve of threshold versus cluster count (or singleton count) and find the “elbow” point.
  • Steep decline phase: As the threshold relaxes, cluster count drops rapidly (many tiny clusters merge).
  • Flat plateau phase: Cluster count changes stabilize.
  • Elbow point: The point where the curve changes from “steep” to “flat,” usually corresponding to the data’s inherent natural structure.
• Operation:
  1. Run scan: necom cut scan-simple ... --range ... > scan.tsv
  2. Observe the rate of change: if cluster count changes sharply when the threshold increases from $T_1$ to $T_2$ but flattens from $T_2$ to $T_3$, then $T_2$ may be the best cut point.
  3. Visualization: Import scan.tsv into plotting tools to assist judgment.

Strategy 3: Evaluation-Metric Based

This is the most rigorous strategy, using necom eval partition to compute clustering quality metrics.

• Principle: Directly compute internal validity (e.g., Silhouette) or external consistency (e.g., ARI, if Ground Truth is available) of the partition.
• Operation: Use together with necom eval partition.

  # Generate detailed list of all candidate partitions
  necom cut scan-simple tree.nwk --height --range ... > partitions.tsv
  # Batch evaluation
  necom eval partition partitions.tsv --input-format long --matrix dist.phy
  

Existing Tool References

The design of necom cut draws on best practices from multiple fields:

• SciPy (scipy.cluster.hierarchy):
  • Provides the fcluster function, supporting cuts by height (distance), cluster count (maxclust), and inconsistency coefficient (inconsistent).
  • necom reuses its definitions of height and inconsistent.
• R (dynamicTreeCut):
  • Provides cutreeDynamic (Tree) and cutreeHybrid (Hybrid) methods.
  • Introduces the ideas of “adaptive recursive cutting” and “core detection + reassignment.”
  • necom fully implements its Dynamic Tree and Hybrid algorithms, providing a high-performance Rust version.
• TreeCluster:
  • Designed specifically for phylogenetic trees, introducing Max Clade (diameter), Avg Clade, etc.
  • Solves cutting problems for non-ultrametric trees.
  • necom fully implements its core algorithm set.
• R (cutree):
  • Provides the most basic h (height) and k (number of clusters) cuts.

necom mat

The necom mat module focuses on the manipulation and conversion of distance matrices. It is the upstream data preparation and preprocessing toolkit for necom clust (clustering and tree inference).

Core Purpose

• Input/Output: Primarily handles PHYLIP format distance matrices (dense) and Pairwise TSV(sparse list) format.
• Functionality: Format conversion, subset extraction, matrix comparison, and standardization.
• Goal: Provide standard, efficient data interfaces for phylogenetics and statistical clustering.

Scope

necom currently focuses on clustering, distance matrix processing, and phylogenetic tree operations. Supported file formats are limited to those actually used by these commands.

Distance matrices and Newick trees do not carry genomic coordinates. If other necom commands require coordinate-based input, this is documented separately in the corresponding command documentation.

Supported Formats and Data Structures

necom supports two external distance matrix file formats: PHYLIP and Pairwise.

1. PHYLIP Distance Matrix (Dense)

The PHYLIP distance matrix format is a common format in phylogenetic analysis. necom provides a series of tools for processing this format.

necom stores this internally using the NamedMatrix structure, backed by CondensedMatrix (a one-dimensional array storing the upper triangle, excluding the diagonal), with memory usage of approximately $N(N-1)/2$ values, i.e. $O(N^2)$.

necom supports both Strict and Relaxed PHYLIP formats.

Relaxed PHYLIP (default input support):

• First line: optional number of samples. If omitted, the program infers the size from the data rows.
• Data rows: sample name followed by distance values.
• Separators: whitespace characters (spaces or tabs).
• Matrix form: supports full square matrix or lower triangular matrix. The lower-triangular form may either include the diagonal (row i has i+1 values) or omit it (row i has i values), in which case the diagonal is assumed to be 0.0.
• Name length: not restricted.
• Note: a first line that is a single integer is always interpreted as the optional sequence-count header. To use a purely numeric sequence name on the first line, prepend an explicit count header, or make sure the first line also contains distance values (full or lower-with-diagonal layouts). For lower-triangular matrices without diagonal values, numeric names must be preceded by an explicit count header.

Strict PHYLIP (strict mode output):

• Follows the original PHYLIP standard.
• Sequence names: strictly truncated to 10 bytes, left-aligned and space-padded.
• Numeric format: space-separated, usually kept to 6 decimal places.

Variants:

• Full: Standard $N \times N$ matrix including the redundant symmetric portion.
• Lower-triangular: Only the lower-triangle portion, reducing file size by half.

2. Pairwise TSV (Sparse List Form)

The Pairwise format is a simple three-column TSV format for representing pairwise distances between sequences, commonly used as an intermediate format or input for graph data.

Sparse or list-form distance data, suitable for storing graph structures or only a subset of pairs.

• Format: tab-separated three columns: name1\tname2\tdistance
• Characteristics:
  • Suitable for sparse graphs or as an exchange format with other tools (e.g., BLAST/MMseqs2).
  • When converting to a matrix, unlisted pairs are treated as missing values or defaults.

necom provides mutual conversion between matrix and Pairwise list:

• Matrix to Pair (necom mat to-pair): flatten a PHYLIP matrix into a Pairwise list.
• Pair to Matrix (necom mat to-phylip): assemble a Pairwise list back into a PHYLIP matrix, supporting --missing and --same parameters.

Internal Data Structures

necom uses three internal matrix representations. Understanding their trade-offs helps explain why different commands expect different input formats and why some operations are more memory-efficient than others.

NamedMatrix

A dense, named distance matrix used for PHYLIP input/output. It stores:

• An IndexMap<String, usize> mapping sequence names to row/column indices.
• A CondensedMatrix holding the upper-triangular pairwise values.
• An optional diagonal vector, required by transformations such as necom mat transform --normalize.

NamedMatrix is the in-memory representation after loading a PHYLIP file. For $N = 10{,}000$, the underlying CondensedMatrix holds roughly 50 million f32 values, or about 200 MB.

CondensedMatrix

A memory-efficient dense matrix used directly by hierarchical clustering algorithms such as necom clust hier. It stores only the upper triangle (excluding the diagonal) of a symmetric matrix in a single Vec<f32>:

$$ k = N \cdot \text{row} - \frac{\text{row}(\text{row}+1)}{2} + \text{col} - \text{row} - 1, \quad \text{row} < \text{col} $$

The diagonal is implicitly 0.0, and the matrix is symmetric. This is the standard condensed distance matrix layout used by many statistical packages (e.g., SciPy) and by the NN-chain implementation in necom clust hier.

ScoringMatrix

A sparse matrix for graph-based algorithms (e.g., DBSCAN, MCL) and partial pairwise data. It stores only explicitly set values in a HashMap<usize, T>, using a single compressed key for the lower triangle including the diagonal:

$$ \text{key}(i, j) = \frac{j(j+1)}{2} + i, \quad i \le j $$

Because this key depends only on i and j, not on the matrix size N, entries remain valid even when the inferred size grows as more samples are discovered.

Subcommands in Detail

Format Conversion

necom mat to-phylip

Build a full PHYLIP distance matrix from a pairwise TSV (e.g., alignment output). Missing pairs can be filled with --missing and self-pairs with --same.

necom mat to-pair

Flatten a PHYLIP matrix into a three-column pairwise TSV (A B distance), emitting the lower triangle including the diagonal.

necom mat format

Convert a PHYLIP matrix into another PHYLIP variant while preserving all distance values.

• --format full (default): full square matrix with original names.
• --format lower: lower-triangular matrix without diagonal values.
• --format strict: 10-character names and fixed-width values for compatibility with the original PHYLIP toolkit.

Operations and Analysis

necom mat subset

Extract a PHYLIP submatrix in the order of a given ID list.

necom mat compare

Compare two matrices on their common IDs using correlation, error, or distance metrics. Multiple --method values can be comma-separated.

necom mat transform

Apply mathematical transformations to matrix elements. It is the main tool for converting a Similarity Matrix into a Distance Matrix, and also supports normalization and other numerical adjustments.

Clustering algorithms (UPGMA, NJ, Ward) and multidimensional scaling require a Distance Matrix with $D(x, x) = 0$, $D(x, y) \ge 0$, and smaller values indicating higher similarity. Upstream tools such as BLAST, MMseqs2, and Diamond usually output Similarity, where $S(x, x) = Max$ and larger values indicate higher similarity.

Key options:

• --op: linear, inv-linear, log, exp, square, sqrt.
• --max-val <V>: maximum value for inv-linear (default: 1.0).
• --scale <V>: scale factor for linear (default: 1.0).
• --offset <V>: offset value for linear (default: 0.0).
• --normalize: scale values by diagonal elements before transformation.
• --input-format pair: read pairwise TSV instead of PHYLIP.

necom mat from-vector

Calculate pairwise similarity/distance between vectors in input file(s). Reads the name<tab>v1<tab>v2<tab>... feature-vector format and emits a three-column pairwise TSV (name1<tab>name2<tab>score) suitable for piping into necom mat to-phylip or directly into clustering commands.

• --mode: euclid, cosine, jaccard.
• --binary: treat values as 0/1 before computing.
• --sim / --dis: convert between distance and (dis) similarity.
• Accepts one file (self-comparison) or two files (cross-comparison).
• --parallel <N>: number of worker threads (default 1). With --parallel > 1, rows may be emitted in non-deterministic order.

Conversion Models

necom mat transform supports common similarity-to-distance conversions:

1. Linear Inversion

For similarities with a fixed upper bound:

$$ D = \text{Max} - S $$

Examples: BLAST identity (0–100) becomes $D = 100 - S$; fractions become $D = 1 - S$.

2. Normalized Linear Inversion

For raw scores without a fixed upper bound, normalize by diagonal self-scores first:

$$ D = 1 - \frac{S(x, y)}{\sqrt{S(x, x) \cdot S(y, y)}} $$

A simpler alternative uses the global maximum: $D = 1 - S(x, y) / Max(S)$.

3. Logarithmic

For probabilities or multiplicative models:

$$ D = -\ln(S) $$

After normalization: $D = -\ln(S(x, y) / \sqrt{S(x, x) \cdot S(y, y)})$. Useful for converting sequence identity probability to evolutionary distance.

Notes

• Diagonal information is preserved so that --normalize can use self-scores. If the input lacks diagonal values, --normalize will not work correctly.
• log of NaN propagates NaN for both off-diagonal and diagonal values.
• log of 0 or negative off-diagonal values produces Inf; non-positive diagonal values become 0.
• --normalize warns when diagonal values are NaN or Inf and treats them as zero for that row and column.

Future Work

The following conversions are not yet implemented:

• Reciprocal: $D = 1/S - 1/Max$ (cannot be approximated with --op linear, which is an affine transform).
• Matrix-level Cosine Similarity conversion: $D = 1 - \cos(\theta)$.
• Matrix-level Correlation conversion: $D = \sqrt{2(1 - r)}$ or $D = 1 - r$.

For Cosine/Correlation distances, the workflow depends on the input form:

• Vector-level (one row per sequence with a feature vector): use necom mat from-vector --mode cosine to produce a pairwise TSV directly.
• Matrix-level (already assembled PHYLIP similarity matrix): no built-in conversion is provided; compute in Python (SciPy) and export as a PHYLIP matrix.

Recommended Workflows

Scenario A: Tree Inference from BLAST Results

# 1. Parse BLAST results (column 3 = percent identity) into pairwise distances.
#    distance = 100 - identity. Only one direction (A-B) is needed; the matrix is symmetric.
#    Use OFS='\t' so the output is tab-separated (necom expects TSV, not whitespace-separated)
awk -v OFS='\t' '{print $1, $2, 100-$3}' blast.out > pairs.tsv

# 2. Convert to PHYLIP matrix; set unaligned pairs to maximum distance 100
necom mat to-phylip pairs.tsv --missing 100 -o matrix.phy

# 3. Build NJ tree
necom clust nj matrix.phy > tree.nwk

Scenario B: Extract Subset for Fine-Grained Analysis

# 1. Prepare a list of IDs of interest
cat interesting_ids.txt
# gene_A
# gene_B
# ...

# 2. Extract submatrix from a whole-genome distance matrix
necom mat subset genome_dist.phy interesting_ids.txt -o sub_matrix.phy

# 3. Analyze the subset with Ward clustering
necom clust hier sub_matrix.phy --method ward > sub_tree.nwk

Scenario C: Evaluate Consistency Between Two Distance Calculation Methods

# Compare distance matrices based on K-mer (mash) and alignment (ani)
necom mat compare mash_dist.phy ani_dist.phy --method pearson,spearman

# stdout (tab-separated):
Method	Score
pearson	0.985432
spearman	0.971234

# stderr (info-level logging):
# Sequences in matrices: 100 and 100
# Common sequences: 100

Scenario D: Prepare Data for the Phylip Software Package

# Convert a long-name matrix to strict Phylip format
necom mat format modern.phy --format strict -o input.infile

# Then run neighbor (the original Phylip program)
neighbor < input.infile

necom nwk

necom nwk provides a complete set of tools for processing Newick-format phylogenetic trees, covering information extraction, structural manipulation, and visualization.

Subcommands

Subcommands are grouped into three categories:

• Information: Extract information or statistics from trees.
  • distance: Compute distances between nodes.
  • label: Extract labels/names from the tree.
  • stat: Print tree statistics (node count, leaf count, balance indices, etc.).
• Manipulation: Modify tree structure.
  • order: Reorder nodes (ladderize, alphabetical).
  • prune: Remove nodes (and their descendants/ancestors).
  • rename: Rename specified nodes.
  • replace: Batch replace names or comments from a file.
  • reroot: Reroot the tree.
  • subtree: Extract a specified clade/subtree.
  • topo: Modify topology (remove branch lengths or labels).
• Visualization: Format and visualize output.
  • comment: Add visualization comments.
  • indent: Format Newick with indentation.
  • to-dot: Convert to Graphviz DOT format.
  • to-forest: Convert to LaTeX Forest code.
  • to-svg: Convert to SVG format.
  • to-tex: Generate a complete LaTeX document.

Information Commands

distance

Compute distances between nodes or generate a distance matrix. Use --mode to select root, parent, pairwise, lca, or phylip output.

label

Extract labels (names) from the tree.

stat

Print tree statistics.

Manipulation Commands

order

Sort children of each node without changing topology.

prune

Remove selected nodes from the tree.

rename

Rename specified nodes.

replace

Batch replace node names or append annotations from a TSV file. Use --mode to choose label, taxid, species, or asis replacement.

reroot

Reroot the tree. The default is midpoint rooting; use -n to specify the ingroup, rerooting on the edge leading to the LCA of the specified nodes.

subtree

Extract the subtree rooted at the LCA of selected nodes, or condense it into a single node with --condense.

topo

Modify tree topology and properties, such as removing branch lengths or labels.

Visualization Commands

comment

Add visualization comments or attributes to selected nodes.

indent

Format a Newick tree with indentation or compact output.

to-dot

Convert to Graphviz DOT format.

to-forest

Convert to LaTeX Forest code.

to-svg

Convert to SVG format. Draws a phylogram when branch lengths exist; otherwise draws a cladogram.

to-tex

Wrap a Newick tree in a complete LaTeX document.

Label Handling

• Unquoted labels are trimmed: leading and trailing whitespace is removed. Internal whitespace is preserved only when the label is quoted with single or double quotes.
• Labels containing Newick reserved characters (( ) : ; , [ ]) or whitespace must be quoted to round-trip correctly.
• Single quotes inside single-quoted labels are escaped by doubling (''), and double quotes inside double-quoted labels are escaped by doubling ("").
• Name-based selection filters (-n, -l, -x, --lca) generally log a warning and continue when a requested name is not found, rather than abort. This applies to commands such as distance, label, rename, subtree, comment, and prune.
• order --name-list is an exception: entries in the name list that are not found among the leaf names cause the command to fail with an error listing the missing names.
• reroot is also an exception: if none of the names specified with --node are found, it reports an error and exits, because there is no valid target for rerooting.

Branch Length Handling

necom nwk treats non-finite branch lengths (NaN, positive/negative infinity), negative values, and zero values as 0.0 during computation and visualization. On input, such values are normalized to None (no length annotation); on output, None and zero (0.0) lengths are omitted so that cladograms remain unannotated. This applies to:

• Statistics (stat) and distance calculations (distance).
• Tree operations such as reroot, collapse, and insert_parent.
• Visualization (to-svg, to-dot, to-forest, to-tex).

This normalization prevents invalid values from polluting sums, maxima, or distance computations. Note that input files themselves are not modified; normalization occurs only during internal computation. If strict branch-length validation is needed, clean the data in the input first.

Length detection and distance threshold

• stat counts an edge as “with length” only when its branch length is a positive finite value. Missing, zero, and non-finite lengths are reported as “without length”.
• distance in root, parent, pairwise, and lca modes uses the sum of branch lengths only when its absolute value exceeds 1e-9; otherwise it falls back to the topological edge count. This avoids treating near-zero floating-point values as meaningful distances.
• distance --mode phylip uses a tree-wide decision: if any edge in the tree carries a positive finite length, the full matrix is computed from branch lengths; otherwise it falls back to topological edge counts for all pairs.

Planned Subcommands

• condense: Tree condensation functionality is currently provided by necom nwk subtree --condense; no standalone condense subcommand is planned at this time.
• match, ed, duration: Mapped from newick_utils but not yet implemented in necom nwk; no concrete plan at this time. gen (random tree generation) is decided not to be implemented — see notes/design/nwk-planned.md.
• Tree evaluation (geometric, taxonomic, phylogenetic, trait consistency) is planned as a top-level command necom eval. nwk compare and nwk support have been migrated to necom eval compare and necom eval replicate; see docs/eval.md. The eval tree subcommand remains in design — see notes/design/eval-planned.md.

LaTeX Forest Output

necom nwk to-forest and necom nwk to-tex convert Newick trees into LaTeX code using the Forest package. This is useful for producing publication-quality phylogenetic trees directly from the command line.

• to-forest emits raw Forest code that can be embedded into an existing LaTeX document.
• to-tex generates a complete .tex document by merging the Forest code with a built-in template, ready for compilation with xelatex or tectonic.

Core Commands

necom nwk to-forest

Generates raw LaTeX Forest code.

necom nwk to-forest tree.nwk

Use --bl to draw a phylogram with branch lengths instead of a cladogram:

necom nwk to-forest tree.nwk --bl

necom nwk to-tex

Generates a complete LaTeX document.

necom nwk to-tex tree.nwk -o tree.tex

Compile the output:

tectonic tree.tex
# or
latexmk -xelatex tree.tex

Use --forest to pass through an existing Forest code file instead of a Newick tree:

necom nwk to-tex forest.tex --forest -o document.tex

Style System

Styles are attached to nodes as NHX annotations. The template defines four core visual attributes:

dot

Draws a filled circle at the node.

[&&NHX:dot=red]

When no color is given, dot is automatically applied to named internal nodes.

bar

Draws a short perpendicular bar on the edge between the node and its parent. Useful for marking events or character-state changes.

[&&NHX:bar=blue]

rec

Draws a background rectangle behind the entire clade rooted at the node.

[&&NHX:rec=LemonChiffon]

This is often combined with the soft palette defined in the template.

tri

Draws a triangle to the right of the node, commonly used for collapsed clades or to emphasize a leaf.

[&&NHX:tri=green]

Colors and Global Settings

The built-in template provides a soft, muted palette (for example ChampagnePink, TeaRose, and Celadon). By default:

• tier=word is enabled, aligning all leaf nodes at the same level (cladogram style).
• Branch lines are gray (1 pt).
• Nodes are drawn as small black circles (2 pt).
• A sans-serif font is used.

Font behavior:

• By default, the template uses Noto Sans, which is widely available.
• Use --no-default-style to keep the template’s original Fira Sans / Source Han Sans SC setup instead of injecting the default Noto Sans configuration.

Advanced Features

Phylogram Mode (--bl)

When the input tree contains branch lengths, --bl produces a phylogram with a automatically computed scale bar. The scale values (e.g., 0.01, 0.05, 1.0) are chosen based on the tree height and rendered in the lower-right corner.

Forest Pass-Through (--forest)

to-tex --forest allows an externally generated Forest code file to be wrapped in the template. This is useful when the Forest code has been produced by to-forest and then manually adjusted.

Special Character Handling

LaTeX special characters and Newick conventions are normalized automatically:

• Underscores (_) in node names are replaced with spaces.
• LaTeX special characters ({ } \ # $ % & ~ ^) in node names, labels, comments, and visualization attributes are escaped.

This ensures that the generated Forest code compiles without manual cleanup.

Workflow Example

1. Annotate the tree with visualization attributes:

necom nwk comment input.nwk --lca A,B --rec TeaRose --label Group1 > annotated.nwk

2. Generate the LaTeX document:

necom nwk to-tex annotated.nwk -o output.tex

3. Compile:

tectonic output.tex

Requirements

Compiling to-tex output requires a LaTeX installation that includes:

• fontspec
• xeCJK (for East Asian characters)
• forest

Tectonic is the recommended compiler, but latexmk -xelatex also works.

necom eval

necom eval provides evaluation metrics for clustering partitions and phylogenetic trees. It is the unified entry point for assessing result quality, support, and consistency.

Design Principles

• Unified entry point: All evaluation capabilities live under necom eval, making them easier to discover.
• Evaluation only: eval measures existing results; it does not generate clusters, infer trees, or convert formats.
• Strict validation: External evaluation requires matching sample sets; internal evaluation requires every partition sample to be present in the supplied matrix, tree, or coordinate file. This prevents silent sample dropping and misleading NaN metrics.
• Shared implementation: Metrics are implemented once in libs/eval and reused across commands (e.g., silhouette_score is used by both eval partition --matrix/--tree and the planned eval tree).

Subcommands

Subcommands are grouped by evaluation target:

• Tree comparison:
  • compare: Compare trees (RF, WRF, KF distances).
• Partition evaluation:
  • partition: Evaluate clustering partitions (external and internal metrics).
• Branch support:
  • replicate: Assign support values from replicate trees.

Tree Comparison

compare

Compare trees using Robinson-Foulds (RF) distance and its variants. Supports pairwise comparison within a single file and cross-comparison between two files.

Partition Evaluation

partition

Evaluate clustering partition quality. Supports external comparison to a reference partition (ARI, AMI, V-Measure, FMI, NMI, Jaccard, etc.) and internal evaluation using a distance matrix, tree, or coordinate matrix (Silhouette, Dunn, Davies-Bouldin, Calinski-Harabasz, etc.). Batch mode evaluates multiple partitions from parameter scans.

Input validation is strict: empty partitions are rejected, external evaluation requires matching sample sets, and internal evaluation requires every partition sample to be present in the supplied matrix, tree, or coordinate file. These checks prevent silent sample dropping and misleading NaN metrics.

See docs/eval-partition.md for detailed metric definitions and the selection guide.

Branch Support

replicate

Assign support values to internal nodes of a target tree based on replicate trees (e.g., from bootstrap or jackknife resampling). Outputs the annotated tree (Newick). All trees must share the same leaf set.

Branch Length Handling

necom eval compare normalizes non-finite branch lengths (NaN, positive/negative infinity) and negative values to 0.0 during computation; zero values are left as 0.0. This normalization prevents invalid values from polluting WRF and KF distance computations. Input files themselves are not modified.

Planned Subcommands

The following subcommands are not yet implemented. Their CLI surface is not yet finalized; the descriptions below reflect the current design direction, not commitments. See notes/design/eval-planned.md for design status.

tree (Not Implemented)

Multi-dimensional evaluation of a single phylogenetic tree. The tree is the positional primary input; a partition (--part), reference tree (--ref), trait map (--traits), or original distance matrix (--dist) may be supplied as auxiliary context.

Four evaluation dimensions:

• Geometry: Silhouette, Diameter, AvgDist, MinInterDist. Branches on whether the partition corresponds to tree clades — O(N) for clade groups (e.g., necom cut output), O(N²) for arbitrary partitions (e.g., dbscan/mcl output).
• Trait: Purity, Entropy, DominantTrait — consistency with external labels (taxonomy, geography, phenotype).
• Phylo: Local RF to reference tree, Monophyly Check, ConflictScore.
• Fit: Cophenetic Correlation against an original distance matrix.

Input and output details:

• Tree: Newick (positional argument).
• Partition (--part): optional grouping in cluster or pair format. If omitted, the whole tree is evaluated or a partition is generated via --cut.
• Trait map (--traits): TSV with LeafName <tab> Trait1,Trait2..., used for purity/entropy calculations.
• Reference tree (--ref): Newick species tree for Local RF and monophyly checks. Gene trees typically sample only a subset of taxa, so leaf-set intersection pruning is required before comparison.
• Original matrix (--dist): PHYLIP square matrix or pair TSV for Cophenetic correlation.
• Output: TSV with column groups:
  • Basic: Size, Diameter, AvgDist.
  • Geom: Silhouette, Separation.
  • Trait: Purity, Entropy, DominantTrait.
  • Phylo: RF-Distance (to reference), ConflictScore.
  • Fit: CopheneticCorrelation.
• --metrics: controls which column groups are emitted (e.g., --metrics basic,geom or --metrics cophenet), avoiding unnecessary computation.

Performance notes:

• For clade-aligned partitions, geometry metrics are O(N); for arbitrary partitions they are O(N²).
• Cophenetic correlation is inherently O(N²) because it must compare every leaf pair.
• For large trees, Silhouette supports --samples to estimate geometry metrics without full O(N²) computation.

boot (Not Implemented)

Multiscale bootstrap (pvclust-style) support values for hierarchical clustering. Takes an observation matrix, resamples features at multiple scales, rebuilds the hierarchical tree each time, and fits BP/AU/SI values for every internal node. Design details are in notes/design/eval-boot.md.

quartet (Future Candidate, Not Designed)

Quartet-based consistency or support values for branches. Not yet designed; the namespace is not reserved. Boundary: if the goal is to infer a new tree from quartets, it belongs to nwk; if the goal is to assess branch support of a given tree, it belongs to eval.

Overlapping Features and Boundaries

Several planned and existing subcommands address superficially similar questions. This section clarifies the boundaries to help choose the right command.

eval tree vs eval partition --tree

Both can compute Silhouette from tree distances — in fact eval tree reuses the same silhouette_score implementation as eval partition via the TreeDistance adapter. The difference is the primary subject and the scope of metrics:

Rule of thumb: If the question is “how good is this clustering?”, use eval partition. If the question is “how good is this tree, possibly in the context of some grouping?”, use eval tree.

eval tree --ref vs eval compare

Both compute Robinson-Foulds distances, but at different scopes and for different purposes:

• eval compare: Global tree-to-tree topology comparison. Takes two trees (or two sets of trees) , computes RF/WRF/KF on the full leaf sets. No grouping concept. Supports batch cross-comparison between files.
• eval tree --ref: Local comparison in the context of a partition. The reference tree (typically a species tree) provides biological ground truth. Computes Local RF (cluster subtree vs reference subset) and Monophyly Check (do cluster members form a clade on the reference?). Requires leaf-set intersection pruning as a prerequisite, because gene trees usually sample only a subset of the species tree’s taxa.

Rule of thumb: If comparing two trees as a whole, use eval compare. If assessing whether a gene tree’s clusters are consistent with a species tree, use eval tree --ref.

eval quartet (future) vs eval compare

• eval compare: Topology-based (split-set symmetric difference). Pure structural comparison of whole trees.
• eval quartet (future): Quartet-based, can incorporate sequence alignment. Assesses branch-level support rather than overall distance.

Rule of thumb: eval compare answers “how different are these two trees?”; eval quartet answers “how well-supported is each branch of this tree?”.

eval replicate vs eval compare

• eval compare: Pairwise comparison of given trees. Outputs TSV with RF/WRF/KF distances — a global tree-to-tree difference measure.
• eval replicate: Assigns branch-level support values to a target tree from replicate trees. Outputs the annotated tree (Newick), not a distance table.

Rule of thumb: eval compare measures whole-tree topological difference; eval replicate measures per-branch support from replicates.

Parameter naming: --part vs --tree

The same option names appear under different subcommands with reversed roles, reflecting the primary-subject difference. This is intentional but can be confusing:

• eval tree --part <FILE>: the tree is the positional primary; --part supplies an optional grouping to evaluate on the tree.
• eval partition --tree <FILE>: the partition is the positional primary; --tree supplies an optional distance source for internal metrics.

The option always refers to the auxiliary input. When in doubt, identify which input is the positional argument — that is the subject of the evaluation.

History

• eval partition was migrated from necom clust eval (2026-07).
• eval compare was migrated from necom nwk compare (2026-07).
• eval replicate was migrated from necom nwk support (2026-07).

necom eval partition

This document describes the design philosophy, metrics, and selection guidance for necom eval partition. For command-line options and usage examples, see docs/help/eval/partition.md.

Design Philosophy

necom adopts a componentized design philosophy, separating cluster generation from evaluation. This differs from the integrated design of the Python package clusteval:

• Python clusteval: The fit() method internally performs Grid Search (trying different $k$ or $\epsilon$), computes internal metrics (e.g., Silhouette), and returns the optimal result.
• necom workflow:
  1. Generate: Use necom cut scan-simple to generate a series of candidate partitions (necom clust dbscan’s --scan is not yet implemented).
  2. Evaluate: Use necom eval partition to compute evaluation metrics for these candidates in batch.
  3. Decide: The user selects the optimal parameters based on metrics (e.g., Silhouette peak, Elbow point).
• Complementary:
  • necom eval tree [planned]: Focuses on consistency between tree structure and grouping (geometry/evolution).
  • necom eval partition: Focuses on the statistical validity of partitions, supporting external (two-group comparison) and internal (single group + matrix/coordinates/tree) evaluation.
• Scenarios:
  • Algorithm comparison: Compare result differences between MCL and K-Medoids on the same dataset.
  • Benchmarking: Compare clustering results against known standard classifications (Ground Truth) to compute accuracy.
  • Parameter tuning: Compare stability of clustering results under different parameters (e.g., eps or inflation).

This design allows evaluation tools to exist independently of clustering algorithms, supporting clustering results from any source.

Input Validation

necom eval partition validates inputs before computing metrics to avoid silent failures:

• Empty partitions: A single partition or any batch group with no samples is rejected.
• External evaluation (--other / --truth): The two partitions must contain exactly the same sample set. The command errors out rather than intersecting keys silently.
• Internal evaluation (--matrix, --tree, --coords): Every sample in the partition must be present in the distance source. Missing samples produce a clear error instead of NaN metrics.
• --no-singletons: Singleton clusters are removed from the reference partition first; samples that become unreferenced are excluded from evaluation, and the remaining sample sets are still required to match.

Output Format

necom eval partition writes a TSV with a header row followed by one result row.

• External evaluation: one row of pair-based metrics (ari, ami, homogeneity, completeness, v_measure, fmi, nmi, mi, ri, jaccard, precision, recall).
• Distance-based internal evaluation: silhouette, dunn, c_index, gamma, tau, davies_bouldin.
• Coordinate-based internal evaluation: davies_bouldin, calinski_harabasz, pbm, ball_hall, xie_beni, wemmert_gancarski.
• Batch mode (--input-format long): one row per Group, with the Group column preserved as the first column.
• Non-finite metric values (NaN, +Infinity, or -Infinity) are emitted as NA to keep the TSV parseable. This occurs in degenerate cases such as Calinski-Harabasz when clusters are perfectly compact and well-separated, or Xie-Beni when two centroids coincide.

Core Metrics

Clustering evaluation metrics usually fall into two categories: external validity (requires Ground Truth or a reference partition) and internal validity(depends only on the geometry/statistics of the data).

1. External Validity

Used to compare consistency between two clustering results, or to evaluate how well a result matches the true classification.

1.1 Pair-Based

Focuses on whether sample pairs remain in the same/different groups across two partitions.

• ARI (Adjusted Rand Index)
  • Definition: Rand Index corrected for chance.
  • Principle: Counts sample pairs that are in the same or different groups in both partitions, and subtracts the expected value under random assignment.
  • Range: [-1, 1]. 1 means perfect agreement, 0 means random level, negative values mean worse than random.
  • Advantages:
    • Interpretable: 0 is the random baseline, intuitive.
    • Symmetric: ARI(A, B) == ARI(B, A).
  • Disadvantages: Insensitive to internal cluster structure (e.g., shape).
  • Applicable: General scenarios with imbalanced cluster sizes and many clusters.
• RI (Rand Index)
  • Definition: Proportion of correctly classified sample pairs.
  • Range: [0, 1].
  • Disadvantages: Not corrected for chance. As the number of clusters increases, the RI of random partitions also approaches 1, reducing discriminative power. Generally not recommended for standalone use.
• Jaccard Index (Pair-wise)
  • Definition: Among all sample pairs considered in the same group by either partition (TP + FP + FN), the proportion considered in the same group by both partitions (TP).
  • Formula: $J = \frac{TP}{TP + FP + FN}$.
  • Meaning: The Jaccard similarity between set $S_1$ (same-group pairs in P1) and set $S_2$ (same-group pairs in P2).
• Precision (Pair-wise)
  • Definition: Among all sample pairs considered in the same group by the predicted partition (P1), the proportion also considered in the same group by the true partition (P2).
  • Formula: $P = \frac{TP}{TP + FP}$.
• Recall (Pair-wise)
  • Definition: Among all sample pairs considered in the same group by the true partition (P2), the proportion also considered in the same group by the predicted partition (P1).
  • Formula: $R = \frac{TP}{TP + FN}$.
• FMI (Fowlkes-Mallows Index)
  • Definition: Geometric mean of Precision and Recall.
  • Principle: $FMI = \sqrt{\frac{TP}{TP+FP} \times \frac{TP}{TP+FN}}$.
  • Range: [0, 1].
  • Applicable: When both Precision and Recall are important.

1.2 Information-Theoretic

Focuses on the amount of information (entropy) shared between two partitions.

• AMI (Adjusted Mutual Information)
  • Definition: Mutual Information corrected for chance.
  • Principle: Computes shared information between two partitions based on entropy, and subtracts the random expectation.
  • Range: [-1, 1] (typically [0, 1]). 1 means perfect agreement, 0 means random, negative values mean worse than random (e.g., anti-correlated partitions).
  • Advantages:
    • More robust when the number of clusters is very large (even close to the sample size).
    • Captures complex non-linear relationships.
  • Applicable: Small samples, many clusters (Large K) scenarios.
• NMI (Normalized Mutual Information)
  • Definition: Normalized Mutual Information.
  • Principle: $NMI = \frac{MI(U, V)}{\sqrt{H(U) \cdot H(V)}}$ (geometric mean) or $\frac{2 \cdot MI}{H(U) + H(V)}$ (arithmetic mean). necom uses the geometric mean.
  • Range: [0, 1].
  • Disadvantages: Not corrected for chance.
  • Applicable: Scenarios with balanced cluster size distributions.
  • Implementation note: Because NMI is a ratio of MI to the geometric mean of the two entropies, the choice of logarithm base cancels out. The value is therefore independent of whether natural logs or base-2 logs are used.
• MI (Mutual Information)
  • Definition: Mutual information between two partitions.
  • Principle: $MI(U, V) = \sum \sum P(u,v) \log \frac{P(u,v)}{P(u) P(v)}$.
  • Range: [0, +∞).
  • Disadvantages: Difficult to interpret directly; strongly affected by partition entropy. Usually used as an intermediate step for AMI/NMI.
  • Implementation note: The implementation uses natural logarithms (matching scikit-learn), so the raw MI value (in nats) equals the base-2 value (in bits) multiplied by ln(2) (≈ 0.693). Normalized metrics (NMI, AMI, V-Measure) are unaffected because they are ratios.
• Homogeneity
  • Definition: Does each cluster contain only members of a single class? (Similar to Precision, requiring clusters to be “pure.”)
  • Principle: Based on conditional entropy $H(C|K)$. If $H(C|K)=0$, Homogeneity is 1.
  • Range: [0, 1].
• Completeness
  • Definition: Are all members of a class assigned to the same cluster? (Similar to Recall, requiring clusters to be “complete.”)
  • Principle: Based on conditional entropy $H(K|C)$. If $H(K|C)=0$, Completeness is 1.
  • Range: [0, 1].
• V-Measure
  • Definition: Harmonic mean of Homogeneity and Completeness.
  • Range: [0, 1].
  • Disadvantages: Not corrected for chance. With small samples or many clusters, scores tend to be high.
  • Applicable: When you need to analyze the source of clustering error (over-fragmentation vs. over-mixing).

2. Internal Validity

Used to evaluate the quality of a clustering result itself (compactness and separation) without Ground Truth.

2.1 Distance-Based

Requires a distance matrix (--matrix) or a phylogenetic tree (--tree).

• Silhouette Coefficient
  • Principle: For each sample $i$, compute its average distance to samples in the same cluster $a(i)$ and its average distance to the nearest other cluster $b(i)$. $s(i) = (b - a) / \max(a, b)$.
  • Range: [-1, 1].
    • Near 1: sample is well clustered (close to same cluster, far from others).
    • 0: sample lies on a cluster boundary.
    • Negative: sample may be mis-clustered.
  • Implementation note: Following scikit-learn’s convention, samples in singleton clusters contribute $s(i) = 0$ to the average (but are still counted in the divisor $N$). The score is 0.0 when there are fewer than 2 clusters or when every sample is its own cluster.
  • Advantages: Intuitive; balances cohesion and separation.
  • Disadvantages: High computational complexity ($O(N^2)$); requires optimization for large-scale data.
• Dunn Index
  • Principle: Ratio of the minimum between-cluster distance to the maximum within-cluster diameter.
  • Range: [0, +∞). Larger is better.
  • Boundary cases: If the maximum intra-cluster diameter is zero (perfectly compact clusters) and the minimum inter-cluster distance is positive, the score is infinite and is reported as NA. If both are zero, the score is 0.0.
  • Advantages: Simple and intuitive.
  • Disadvantages: Extremely sensitive to noise (because it relies on min/max).
• C-Index
  • Principle: Compares the sum of within-cluster distances with the sum of the smallest $N_W$ distances in the entire dataset ($N_W$ is the number of within-cluster pairs).
  • Range: [0, 1]. Smaller is better.
  • Boundary cases: Returns 0.0 when there are fewer than 2 samples, when there are no within-cluster pairs (all singletons), when all pairs are within-cluster (single cluster), or when all pairwise distances are equal (zero variance in the denominator).
  • Disadvantages: High computational complexity ($O(N^2 \log N)$), requiring sorting of all pairwise distances.
• Hubert’s Gamma
  • Principle: Correlation between the distance matrix and a binary clustering matrix (0 = same cluster, 1 = different clusters).
  • Range: [-1, 1]. Larger is better (Y=1 means different clusters; larger Gamma means between-cluster distances exceed within-cluster distances more strongly).
  • Boundary cases: Returns 0.0 when there are fewer than 2 samples, or when the distance matrix or the clustering matrix has zero variance (degenerate cases such as all-equal distances or a single-cluster partition).
• Kendall’s Tau
  • Principle: Rank correlation coefficient between the distance matrix and the clustering matrix.
  • Range: [-1, 1]. Larger is better.
  • Boundary cases: Returns 0.0 when there are fewer than 2 samples, or when the denominator is zero (degenerate cases with no usable pair comparisons).
• Davies-Bouldin Index (DBI)
  • Principle: Same idea as the coordinate version, but uses medoids (cluster members with the smallest average intra-cluster distance) as cluster representatives because coordinates are not available. scatter_i is the average distance from cluster members to the medoid, and inter-cluster distance is the distance between medoids.
  • Range: [0, +∞). Smaller is better.
  • Boundary cases: If two medoids coincide and at least one cluster has non-zero scatter, the similarity is undefined; a large finite proxy (1e10) is used so the TSV remains parseable.

2.2 Coordinate-Based

Requires a coordinate matrix (--coords). Suitable for Euclidean-space data.

• Davies-Bouldin Index (DBI)
  • Principle: Computes the “similarity” of each cluster pair (within-cluster dispersion sum / centroid distance), then takes the mean of each cluster’s worst (largest) similarity.
  • Range: [0, +∞). Smaller is better.
  • Boundary cases: If two cluster centroids coincide and at least one has non-zero scatter, the similarity is undefined (infinite). The implementation substitutes a large finite proxy (1e10) so the TSV remains parseable.
  • Advantages: Faster than Silhouette.
  • Applicable: Evaluating centroid-based clustering algorithms.
• Calinski-Harabasz Index (CH)
  • Principle: Ratio of between-cluster dispersion (BGSS) to within-cluster dispersion (WGSS).
  • Range: [0, +∞). Larger is better.
  • Advantages: Fast to compute.
  • Boundary cases:
    • If every point is identical (WGSS == 0 and BGSS == 0), the input is degenerate and the score is 0.0.
    • If clusters are perfectly compact and well-separated (WGSS == 0 but BGSS > 0), the score is infinite and is reported as NA to keep the TSV parseable.
• PBM Index
  • Principle: Composite index based on total dispersion, within-cluster dispersion, and maximum centroid distance.
  • Range: [0, +∞). Larger is better.
  • Boundary cases:
    • If within-cluster dispersion is zero while total dispersion is positive (perfectly compact clusters), the score is infinite and is reported as NA to keep the TSV parseable.
    • If both within-cluster and total dispersion are zero (all points coincide with the global centroid — degenerate input), the score is 0.0.
• Ball-Hall Index
  • Principle: Mean of average within-cluster dispersions.
  • Range: [0, +∞). Smaller is better (more compact).
• Xie-Beni Index
  • Principle: Ratio of within-cluster compactness to between-cluster separation (minimum centroid distance).
  • Range: [0, +∞). Smaller is better.
  • Boundary cases: If the closest pair of cluster centroids coincide, separation is zero and the score is infinite; it is reported as NA to keep the TSV parseable.
• Wemmert-Gancarski Index
  • Principle: Compactness index based on relative distances (distance to own centroid / distance to nearest other centroid).
  • Range: [0, 1]. Larger is better.
  • Boundary cases: If a point coincides with another cluster’s centroid (inter-cluster distance is zero), a penalty (10.0) is applied to the ratio so the index remains finite.

Metric Selection Guide

See Also

• necom clust for command overview, supported algorithms, and partition/matrix/coordinate format conventions.
• docs/help/eval/partition.md for the command-line help text, including available options and usage examples.

necom pl

The necom pl module provides integrated pipelines that combine multiple necom operations into a single command.

Currently, only one pipeline is implemented:

• condense: Condense monophyletic subtrees based on a taxonomy TSV file.

For command-line options and usage examples, see docs/help/pl/condense.md.

Full Example with Test Data

necom pl condense --taxon tests/pipeline/strains.taxon.tsv \
    tests/pipeline/minhash.reroot.newick

necom File Formats

necom commands share a small set of file formats for clustering results, distance matrices, feature vectors, and phylogenetic trees. This document describes the common formats and points to command-specific details where applicable.

• For distance-matrix conversion and manipulation, see docs/mat.md.
• For Newick tree conventions (label quoting, branch-length handling), see docs/nwk.md.
• For scan-mode partition output, see docs/cut.md.

Partition Files

Used to represent clustering results (sample-to-cluster mapping). Three formats are supported via the --format option.

Pair Format (--format pair)

The most general long-table format; each line is a (representative, member) pair.

• Structure: Representative <tab> Member
• Representative selection: For dbscan / mcl / k-medoids, controlled by --rep {medoid|first}; default medoid. cc does not read weights and always uses the alphabetically first member. The representative is written to the first column; the member to the second column. Singletons appear as Name <tab> Name.
• Default format: The default output format for flat clustering commands is cluster; use --format pair to emit this long-table representation.
• Characteristics: Easy to parse; supports streaming.
• Example:

  GeneA	GeneA
  GeneA	GeneB
  GeneC	GeneC
  

Cluster Format (--format cluster)

Wide-table format; each line represents a cluster containing all its members.

• Structure: tab-separated items, one cluster per line.
• Characteristics: Human-readable; suitable for inspecting results. The line number (1-based) is the ClusterID. The first item is the cluster representative when representative selection applies.
• Example:

  GeneA	GeneB
  GeneC
  

Long Format (batch, --format long)

A dedicated TSV format (Group\tClusterID\tSampleID) for batch evaluation, auto-emitted by necom cut scan-simple and necom cut scan-dynamic and consumed by necom eval partition --input-format long. See docs/cut.md for the full specification.

Distance Matrix

Used by clust hier, nj, upgma, eval partition --matrix, and cut hybrid --matrix.

PHYLIP Format

necom accepts a relaxed PHYLIP format (arbitrary whitespace, optional header). See docs/mat.md for full structure, strict vs relaxed variants, and lower-triangular form.

Pairwise TSV

A sparse list representation of pairwise distances or similarities:

• Format: tab-separated three columns: name1\tname2\tdistance
• Characteristics: Suitable for sparse graphs or as an exchange format with other tools (e.g., BLAST/MMseqs2).
• Conversion: Use necom mat to-phylip to assemble into a PHYLIP matrix, and necom mat to-pair to flatten a PHYLIP matrix into this form. See docs/mat.md for details.

Coordinates / Feature Vectors

Used by eval partition --coords (Davies-Bouldin Index) or future kmeans/gmm.

FeatureVector Format

• Structure: Name <tab> Val1 <tab> Val2 <tab> Val3 ... (pure TSV)
• Delimiters: Tab between every pair of adjacent fields.
• Example:

  GeneA	1.2	0.5	3.3
  GeneB	1.1	0.6	3.1
  

• Compatibility: A general feature-vector/coordinate representation format.

Newick Tree Conventions

necom uses the Newick format for phylogenetic and hierarchical-clustering trees. Important conventions include label quoting for reserved characters and normalization of non-finite branch lengths. See docs/nwk.md for the full specification.

cut

Cut a Newick tree into flat clustering partitions.

necom cut is split into five focused subcommands. Run necom cut <subcommand> --help for detailed options.

Input:

• A Newick file containing a single tree.
• Branch lengths are used by distance/height-based methods.
• Branch support values (optional) can be used as a non-crossable constraint via --support.

Subcommands:

• simple: static threshold methods such as k, height, max-clade, avg-clade, inconsistent, etc.
• dynamic: Dynamic Tree Cut (top-down adaptive, --min-size).
• hybrid: Dynamic Hybrid Cut (tree + distance matrix, --min-size, --matrix).
• scan-simple: parameter sweep over a static method threshold.
• scan-dynamic: parameter sweep over dynamic-tree min cluster sizes.

Examples:

1. Cut into 5 clusters necom cut simple tree.nwk --k 5

2. Cut at height 0.5 necom cut simple tree.nwk --height 0.5

3. Dynamic Tree Cut with min cluster size 20 necom cut dynamic tree.nwk --min-size 20

4. Scan thresholds and save statistics necom cut scan-simple tree.nwk --max-clade --range 0,0.5,0.01

simple

Cut a tree using a static threshold method.

Input:

• A Newick file containing a single tree.
• Branch lengths are used by distance/height-based methods.

Output:

• --format cluster (default): each line contains the members of one cluster; the first member is the representative.
• --format pair: each line contains a (representative, member) pair.

Notes:

• Exactly one method option must be provided: --k, --height, --root-dist, --max-clade, --avg-clade, --med-clade, --sum-branch, --leaf-dist-max, --leaf-dist-min, --leaf-dist-avg, --max-edge (--single-linkage), --inconsistent.
• --k must be a positive integer.
• --deep controls the depth used by the inconsistent method (default: 2).
• --rep selects the cluster representative: root (default), first, or medoid.
• --support <S> treats edges with support < S as effectively infinite length, forcing a cut at low-support positions. Nodes without explicit support default to 100.0.
• Distance/height thresholds must be non-negative finite numbers.

Examples:

1. Cut into 5 clusters necom cut simple tree.nwk --k 5

2. Cut at height 0.5 necom cut simple tree.nwk --height 0.5

3. Cut by max pairwise distance necom cut simple tree.nwk --max-clade 0.1

4. Use pair format necom cut simple tree.nwk --k 3 --format pair

dynamic

Cut a tree using Dynamic Tree Cut.

Input:

• A Newick file containing a single tree.
• Branch lengths are used to compute node heights.

Output:

• --format cluster (default): each line contains the members of one cluster; the first member is the representative.
• --format pair: each line contains a (representative, member) pair.

Notes:

• The --min-size option is required and must be a positive integer.
• --deep-split enables more aggressive splitting (default: off).
• --max-tree-height sets the maximum joining height; if omitted, 99% of the tree height is used.
• --rep selects the cluster representative: root (default), first, or medoid.
• --support <S> treats edges with support < S as effectively infinite length, forcing a cut at low-support positions.
• Leaves that fall below the minimum cluster size are labeled as unassigned (cluster 0) and are still emitted.

Examples:

1. Dynamic Tree Cut with min cluster size 20 necom cut dynamic tree.nwk --min-size 20

2. Enable deep split necom cut dynamic tree.nwk --min-size 10 --deep-split

3. Limit maximum joining height necom cut dynamic tree.nwk --min-size 10 --max-tree-height 0.5

hybrid

Cut a tree using Dynamic Hybrid Cut.

Input:

• A Newick file containing a single tree.
• A distance matrix file in relaxed PHYLIP format (--matrix).

Output:

• --format cluster (default): each line contains the members of one cluster; the first member is the representative.
• --format pair: each line contains a (representative, member) pair.

Notes:

• The --matrix and --min-size options are required. --min-size must be a positive integer.
• --max-pam-dist sets the maximum distance for PAM reassignment (optional).
• --no-pam-dendro disables dendrogram respect during PAM reassignment (default: off).
• --deep-split enables more aggressive splitting (default: off).
• --max-tree-height sets the maximum joining height; if omitted, defaults to ref_height + 0.99 * (max_height - ref_height), where ref_height is the 5th percentile of merge heights and max_height is the maximum merge height.
• --rep selects the cluster representative: root (default), first, or medoid.
• --support <S> treats edges with support < S as effectively infinite length, forcing a cut at low-support positions.

Examples:

1. Hybrid cut with min cluster size 20 necom cut hybrid tree.nwk --matrix dist.phy --min-size 20

2. Allow PAM reassignment across high branches necom cut hybrid tree.nwk --matrix dist.phy --min-size 10 --no-pam-dendro

3. Limit PAM reassignment distance necom cut hybrid tree.nwk --matrix dist.phy --min-size 10 --max-pam-dist 0.3

scan-simple

Scan static threshold cut parameters.

Input:

• A Newick file containing a single tree.

Output:

• Always writes the long format table Group\tClusterID\tSampleID.
• If --stats-out is given, also writes a summary table with Group\tClusters\tSingletons\tNon-Singletons\tMaxSize.

Notes:

• Exactly one method flag must be provided: --k, --height, --root-dist, --max-clade, --avg-clade, --med-clade, --sum-branch, --leaf-dist-max, --leaf-dist-min, --leaf-dist-avg, --max-edge (--single-linkage), --inconsistent.
• --range is required and must be start,end,step with comma separators and no spaces.
• --k --range requires integer values and the start must be at least 1.
• --deep controls the depth for the inconsistent method (default: 2).
• Distance/height thresholds must be non-negative finite numbers.
• --support <S> treats edges with support < S as effectively infinite length.
• The --format and --rep options are not available in scan mode.

Examples:

1. Scan heights and save statistics necom cut scan-simple tree.nwk --height --range 0,1.0,0.05 --stats-out stats.tsv > partitions.tsv

2. Scan max-clade thresholds necom cut scan-simple tree.nwk --max-clade --range 0,0.5,0.01

3. Scan cluster counts necom cut scan-simple tree.nwk --k --range 1,5,1

scan-dynamic

Scan Dynamic Tree Cut min cluster sizes.

Input:

• A Newick file containing a single tree.

Output:

• Always writes the long format table Group\tClusterID\tSampleID.
• If --stats-out is given, also writes a summary table with Group\tClusters\tSingletons\tNon-Singletons\tMaxSize.

Notes:

• The --range option is required and must be start,end,step with comma separators and no spaces.
• All three range values must be non-negative integers and the step must be positive.
• start must be at least 1 because the min cluster size must be greater than 0.
• --deep-split enables more aggressive splitting (default: off).
• --max-tree-height sets the maximum joining height; if omitted, 99% of the tree height is used.
• --support <S> treats edges with support < S as effectively infinite length.
• The --format and --rep options are not available in scan mode.
• The output Group column is labeled dynamic-tree=<min-size>.

Examples:

1. Scan min cluster sizes from 2 to 20 necom cut scan-dynamic tree.nwk --range 2,20,2 --stats-out stats.tsv > partitions.tsv

2. Scan with deep split enabled necom cut scan-dynamic tree.nwk --range 2,20,2 --deep-split --stats-out stats.tsv > partitions.tsv

clust

Cluster entries via various algorithms.

Input:

• clust is a command group; use one of its subcommands directly.

Notes:

• Subcommand groups:
  • Tree: hier, nj, upgma
  • Flat: cc, dbscan, k-medoids, mcl, scan-dbscan
• Run necom clust <subcommand> --help for algorithm-specific options.

Examples:

1. Show available subcommands necom clust --help

cc

Cluster entries via connected components.

Input:

• A pairwise TSV file (name1\tname2\t[weight]). Weights are ignored.

Output:

• --format cluster (default): each line contains all points of one cluster.
• --format pair: each line contains a (representative, member) pair.

Notes:

• In pair format, the representative is the alphabetically first member of the cluster.

Examples:

1. Find connected components necom clust cc pairs.tsv

2. Output as pairs necom clust cc pairs.tsv --format pair

dbscan

Cluster entries using DBSCAN.

Input:

• A pairwise distance TSV file (name1\tname2\tdistance). Lower distances indicate higher similarity.

Output:

• --format cluster (default): each line contains points of one cluster.
• --format pair: each line contains a (representative, member) pair.

Notes:

• The input must contain distances, not similarities.
• --eps <V>: neighborhood radius (default: 0.05).
• --min-points <N>: minimum number of points (including the point itself) to form a dense region (default: 4).
• --min-pct <P>: alternative to --min-points; specify the minimum as a fraction of the total number of samples (range (0, 1]). The effective value is ceil(P * n_samples). Mutually exclusive with --min-points.
• --same <V>: default score of identical element pairs (default: 0.0).
• --missing <V>: default score of missing pairs (default: 1.0).
• The representative point is selected by --rep:
  • medoid (default): point with minimum sum of distances to other cluster members.
  • first: alphabetically first member.
• In cluster format, the representative is placed first; in pair format, it is the first column.
• Noise points (points not assigned to any density cluster) are emitted as single-member clusters. In pair format this appears as Name <tab> Name.
• The neighborhood count used by --min-points includes the point itself when --same is 0.0 (default), because self-distance is then 0 and is always <= eps. Setting --same to a value greater than eps excludes the point from its own neighborhood.
• To scan eps values and compare internal metrics, use necom clust scan-dbscan.

Examples:

1. Run DBSCAN with defaults necom clust dbscan pairs.tsv

2. Set epsilon and min-points (min-points default: 4; here set to 5) necom clust dbscan pairs.tsv --eps 0.05 --min-points 5

3. Use –min-pct instead of –min-points necom clust dbscan pairs.tsv --min-pct 0.1

4. Output as pairs necom clust dbscan pairs.tsv --format pair

hier

Perform agglomerative hierarchical clustering on a distance matrix.

Input:

• A PHYLIP format distance matrix (strict or relaxed).
• For pairwise list input (name1\tname2\tdist), use necom mat to-phylip first.

Output:

• A Newick tree string written to stdout or --outfile.

Notes:

• Internal node height is half the linkage distance (height = distance / 2); branch length from child to parent is parent_height - child_height.
• --method <METHOD>: linkage method (default: ward). Supported: single, complete, average (upgma), weighted (wpgma), centroid (upgmc), median (wpgmc), ward (ward.d2).
• For reducible methods (single, complete, average, weighted, ward), the default NN-chain implementation may produce a different merge order than the primitive algorithm, but the resulting partition sequence is equivalent.
• centroid and median linkage may produce non-monotonic merge heights (inversions); branch lengths are clamped at 0.0 so the resulting Newick tree remains valid. The same clamp is applied to all methods as a safety net.
• For Ward’s method, the input is assumed to be Euclidean distances or similar.
• Alias: necom clust hclust is equivalent to necom clust hier.

Examples:

1. Ward’s method (default) necom clust hier matrix.phy > tree.nwk

2. Average linkage (UPGMA) necom clust hier matrix.phy --method average > tree.nwk

3. Single linkage (nearest neighbor) necom clust hier matrix.phy --method single > tree.nwk

k-medoids

Cluster entries using K-Medoids (PAM / Lloyd-like).

Input:

• A pairwise distance TSV file (name1\tname2\tdistance). Lower distances indicate higher similarity.

Output:

• --format cluster (default): each line contains points of one cluster.
• --format pair: each line contains a (representative, member) pair.

Notes:

• The input must contain distances, not similarities.
• --k <N>: number of clusters (required). Must not exceed the number of samples.
• --runs <N>: number of random initializations (default: 10).
• --max-iter <N>: maximum number of iterations (default: 100).
• --seed <N>: random seed for reproducible initialization.
• --same <V>: default score of identical element pairs (default: 0.0).
• --missing <V>: default score of missing pairs (default: 1.0).
• Alias: necom clust km is equivalent to necom clust k-medoids.
• The representative point is selected by --rep:
  • medoid (default): point with minimum sum of distances to other cluster members.
  • first: alphabetically first member.
• In cluster format, the representative is placed first; in pair format, it is the first column.
• If a cluster becomes empty during iteration, it is omitted from the output, so the final number of clusters may be less than k.

Examples:

1. Run K-Medoids with K=3 necom clust k-medoids pairs.tsv --k 3

2. Output as pairs necom clust k-medoids pairs.tsv --k 3 --format pair

3. Reproducible run with seed necom clust k-medoids pairs.tsv --k 3 --seed 42

mcl

Cluster entries using Markov Clustering (MCL).

Input:

• A pairwise similarity TSV file (name1\tname2\tsimilarity). Higher scores indicate higher similarity.

Output:

• --format cluster (default): each line contains points of one cluster.
• --format pair: each line contains a (representative, member) pair.

Notes:

• The input must contain similarities, not distances.
• --inflation <V> / -I: inflation parameter (default: 2.0).
• --prune <V>: pruning threshold; matrix entries smaller than or equal to this are set to zero (default: 1e-5).
• --max-iter <N>: maximum number of iterations (default: 100). Must be greater than 0.
• --same <V>: default score of identical element pairs (default: 1.0).
• --missing <V>: default score of missing pairs (default: 0.0).
• The representative point is selected by --rep:
  • medoid (default): point with maximum sum of similarities to other cluster members.
  • first: alphabetically first member.
• In cluster format, the representative is placed first; in pair format, it is the first column.
• During initialization, input similarities smaller than or equal to 1e-5 (including negative values) are treated as zero and ignored. This initial filtering threshold is independent of the --prune threshold used during iterations.
• Reference: Stijn van Dongen, Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, May 2000.

Examples:

1. Run MCL with defaults necom clust mcl similarities.tsv

2. Adjust inflation necom clust mcl similarities.tsv --inflation 3.0

3. Output as pairs necom clust mcl similarities.tsv --format pair

nj

Construct a phylogenetic tree using Neighbor-Joining (NJ).

Input:

• A PHYLIP distance matrix (relaxed or strict).

Output:

• A Newick tree rooted at the midpoint of the final edge.

Notes:

• NJ is a bottom-up clustering method suitable for variable evolutionary rates.
• For non-additive distance matrices, negative branch lengths are clamped to 0.

Examples:

1. Build tree from matrix necom clust nj matrix.phy -o tree.nwk

2. Pipe matrix from stdin cat matrix.phy | necom clust nj stdin > tree.nwk

upgma

Construct a phylogenetic tree using UPGMA.

Input:

• A PHYLIP distance matrix (relaxed or strict).

Output:

• A rooted Newick tree.

Notes:

• UPGMA assumes an ultrametric (molecular clock): all leaves are equidistant from the root.
• When the input distances violate ultrametricity, the tree is still produced; negative branch lengths are clamped to 0 so the output remains a valid Newick tree.
• For non-ultrametric data, consider necom clust nj (neighbor-joining) instead.

Examples:

1. Build tree from matrix necom clust upgma matrix.phy -o tree.nwk

2. Pipe matrix from stdin cat matrix.phy | necom clust upgma stdin > tree.nwk

mat

Operate on distance matrices.

Input:

• mat is a command group; use one of its subcommands directly.

Notes:

• Subcommands:
  • compare: compare two PHYLIP distance matrices.
  • format: convert between PHYLIP matrix variants.
  • from-vector: calculate pairwise similarity/distance from vector inputs.
  • subset: extract a submatrix using a name list.
  • to-pair: flatten a PHYLIP matrix to pairwise TSV.
  • to-phylip: assemble pairwise TSV into a PHYLIP matrix.
  • transform: apply mathematical transformations to matrix elements.
• Run necom mat <subcommand> --help for command-specific options.
• Reads from stdin if input file is ‘stdin’.

Examples:

1. Show available subcommands necom mat --help

compare

Compare two PHYLIP distance matrices and calculate similarity metrics.

Input:

• Two PHYLIP distance matrices (full or lower-triangular).
• Only the intersection of common IDs is used for comparison.

Output:

• Tab-separated values with two columns: Method and Score.
• One row per requested method.

Notes:

• Available methods:
  • all: calculate all metrics below.
  • pearson: Pearson correlation coefficient (-1 to 1).
  • spearman: Spearman rank correlation (-1 to 1).
  • mae: mean absolute error.
  • cosine: cosine similarity (-1 to 1).
  • jaccard: weighted Jaccard similarity (0 to 1).
  • euclid: Euclidean distance.
• Useful for evaluating consistency between distance calculation methods, or measuring information loss before and after clustering (Cophenetic Correlation).
• Default method is pearson.
• Multiple methods can be requested as a comma-separated list.
• Non-finite scores (NaN / Inf) are emitted as NA to keep the TSV parseable.

Examples:

1. Compare using Pearson correlation necom mat compare matrix1.phy matrix2.phy --method pearson

2. Compare using multiple methods necom mat compare matrix1.phy matrix2.phy --method pearson,cosine,jaccard

format

Convert a PHYLIP matrix between formats.

Input:

• PHYLIP distance matrix (full or lower-triangular).
• Optional first line: number of sequences.
• Each line: sequence name followed by distances.

Output:

• full (default):
  • Full square matrix.
  • Tab-separated values.
  • Original sequence names preserved.
• lower:
  • Lower triangular matrix without diagonal values.
  • Tab-separated values.
  • Original sequence names preserved.
  • Row i contains i tab-separated values.
  • Useful for saving disk space.
• strict:
  • Standard PHYLIP format.
  • Names truncated to 10 bytes.
  • Names left-aligned with space padding.
  • Distances formatted to 6 decimal places, space-separated.
  • Space-separated values.
  • Use this for compatibility with the original PHYLIP toolkit.

Notes:

• strict mode truncates names to 10 bytes and formats distances to 6 decimal places, which can cause name collisions and precision loss.
• full and lower preserve original names without truncation.
• full and lower preserve distance values as-is; strict may round them to 6 decimal places.

Examples:

1. Create a full matrix necom mat format input.phy -o output.phy

2. Create a lower-triangular matrix necom mat format input.phy --format lower -o output.phy

3. Create a strict PHYLIP matrix necom mat format input.phy --format strict -o output.phy

from-vector

Calculate pairwise similarity/distance between vectors in input file(s).

Behavior:

• --mode euclid: Euclidean distance.
• --mode euclid --sim: Euclidean distance converted to similarity.
• --mode euclid --binary: binary Euclidean distance (values treated as 0/1).
• --mode euclid --binary --sim --dis: binary Euclidean distance to dissimilarity.
• --mode cosine: cosine similarity (-1 to 1).
• --mode cosine --dis: cosine distance (0 to 2).
• --mode cosine --binary: binary cosine similarity.
• --mode cosine --binary --dis: binary cosine distance.
• --mode jaccard --binary: Jaccard index.
• --mode jaccard: weighted Jaccard similarity.

Input:

• One or two vector files in name<tab>v1<tab>v2<tab>... format (pure TSV).
• One file: self-comparison (all pairs including diagonal).
• Two files: cross-comparison between the two sets.

Output:

• Three-column TSV: name1<tab>name2<tab>score (6 decimal places), one row per pair.

Notes:

• --binary treats positive values as 1, all others as 0, before computing the score.
• --sim converts a distance to a similarity; --dis converts a similarity to a dissimilarity.
• When both --sim and --dis are given, the conversion is applied in the order distance -> similarity -> dissimilarity.
• --parallel <N> sets the number of worker threads (default 1).
• With --parallel > 1, rows may be emitted in non-deterministic order; each row still pairs the first-file entry with all second-file entries in file order.

Examples:

1. Self-compare vectors with binary Jaccard necom mat from-vector vectors.tsv --mode jaccard --binary

2. Cross-compare two vector sets with cosine distance necom mat from-vector set1.tsv set2.tsv --mode cosine --dis -o out.tsv

subset

Extract a submatrix from a PHYLIP matrix using a list of names.

Input:

• Matrix: PHYLIP distance matrix (full or lower-triangular).
• List: names separated by whitespace (one or more per line).
• Empty lines and lines starting with # in the list file are ignored.

Output:

• A full PHYLIP distance matrix containing only the requested names.
• Rows and columns follow the order given in the list file.

Notes:

• Useful for extracting specific species or gene families from a large matrix.
• Can also be used to reorder a matrix by providing names in the desired order.
• Names in the list that are not found in the matrix are reported as warnings and skipped.

Examples:

1. Create a full submatrix necom mat subset input.phy list.txt -o output.phy

to-pair

Convert a PHYLIP distance matrix to pairwise distances.

Input:

• PHYLIP distance matrix (full or lower-triangular).
• First line can be sequence count (optional).
• Each line: sequence name followed by distances.

Output:

• Tab-separated values (TSV).
• Three columns: name1, name2, distance.
• Lower-triangular output, including the diagonal.

Notes:

• Useful as an edge list for graph clustering (e.g., necom clust mcl) or network visualization (e.g., Cytoscape).

Examples:

1. Convert a PHYLIP matrix necom mat to-pair input.mat -o output.tsv

2. Output to screen necom mat to-pair input.mat

to-phylip

Convert pairwise distances to a PHYLIP distance matrix.

Input:

• Tab-separated values (TSV).
• Three columns: name1, name2, distance.

Output:

• A full PHYLIP distance matrix.
• All observed IDs are collected and arranged into a square matrix.

Notes:

• Typical input comes from alignment results (e.g., blast --outfmt 6).
• Use --same to set the distance for self-to-self pairs (diagonal), default 0.0.
• Use --missing to set the distance for pairs without input records, default 1.0.
• The default missing value represents maximum distance, which is useful for unaligned sequences.

Examples:

1. Convert pairwise distances to a PHYLIP matrix necom mat to-phylip input.tsv -o output.phy

transform

Apply mathematical transformations to matrix elements.

Input:

• PHYLIP distance matrix or pairwise TSV file.
• Use --input-format pair to read pairwise TSV input; useful for processing data from STDIN.

Notes:

• Available operations (--op):
  • linear: val = val * scale + offset.
  • inv-linear: off-diagonal val = max - val; diagonal is set to 0.
  • log: val = -ln(val) (off-diagonal <= 0 becomes Inf; diagonal <= 0 becomes 0).
  • exp: val = exp(-val) (input diagonals of 0 produce output diagonals of 1.0).
  • square: val = val * val.
  • sqrt: val = sqrt(val) (negative values produce NaN).
• Useful for converting similarity matrices to distance matrices.
• Use --normalize to normalize based on diagonal elements before transformation: x_norm(i, j) = x(i, j) / sqrt(x(i, i) * x(j, j)).
  • --normalize requires diagonal data in the input; if absent, every diagonal is treated as 0.0, so off-diagonal values become 0.0 before the selected --op is applied.
  • Diagonal values less than or equal to 1e-9 are treated as zero, producing 0.0 for the corresponding row/column.
  • Normalization is applied before the transformation op: off-diagonal x(i,j) / sqrt(d_i*d_j) then --op, diagonal normalized to 1.0 (or 0.0 if d_i <= 1e-9) then --op.
• When --input-format pair is used, --same and --missing control default diagonal and missing-pair values.
• Default parameter values: --max-val 1.0, --scale 1.0, --offset 0.0.

Examples:

1. Convert Identity (0-100) to Distance (0-1) necom mat transform input.phy --op linear --scale -0.01 --offset 1.0 -o dist.phy

2. Convert Identity (0-100) to Distance (0-100) necom mat transform input.phy --op inv-linear --max-val 100 -o dist.phy

3. Convert Similarity (0-1) to Distance (0-1) necom mat transform input.phy --op inv-linear --max-val 1.0 -o dist.phy

4. Probability to distance with log necom mat transform input.phy --op log -o dist.phy

5. Normalize raw scores then convert to distance necom mat transform raw_scores.phy --normalize --op inv-linear --max-val 1.0 -o dist.phy

nwk

Manipulate, analyze, and visualize Newick trees.

Input:

• A Newick tree file or stdin.

Notes:

• Subcommand groups:
  • Information: stat, label, distance
  • Manipulation: order, prune, rename, replace, reroot, subtree, topo
  • Visualization: comment, indent, to-dot, to-forest, to-svg, to-tex
• Run necom nwk <subcommand> --help for command-specific options.
• Reads from stdin if input file is ‘stdin’.

Examples:

1. Show available subcommands necom nwk --help

comment

Add comments to node(s) in a Newick file.

Input:

• A Newick tree file.

Notes:

• Comments are stored in an NHX-like format (:key=value).
• For named nodes, use --node.
• For unnamed internal nodes, use --lca with two comma-separated names, e.g. --lca A,B.
• Use --string / -s to add a free-form string stored under the string property.
• Visualization options:
  • --color, --label, and --comment-text (--comment) each take one argument.
  • --dot, --bar, --rec, and --tri take zero or one argument. When no value is supplied they use their default color (see below); any other value is passed through as the color directly.
• Defaults when no color is given:
  • --dot / --bar: black
  • --rec: LemonChiffon
  • --tri: white
• Predefined colors for --color, --dot, and --bar:
  • red (188,36,46)
  • black (26,25,25)
  • grey (129,130,132)
  • brown (121,37,0)
  • green (32,128,108)
  • purple (160,90,150)
  • blue (0,103,149)
• Predefined background rectangle colors for --rec:
  • LemonChiffon (251,248,204)
  • ChampagnePink (253,228,207)
  • TeaRose (255,207,210)
  • PinkLavender (241,192,232)
  • Mauve (207,186,240)
  • JordyBlue (163,196,243)
  • NonPhotoBlue (144,219,244)
  • ElectricBlue (142,236,245)
  • Aquamarine (152,245,225)
  • Celadon (185,251,192)
• --remove / -r scans all nodes and removes whole property entries whose serialized key=value (or bare key) matches the regex.

Examples:

1. Add a string comment to a node necom nwk comment tree.nwk --node A --string "bootstrap 90" -o out.nwk

2. Add a colored dot to an internal node via LCA necom nwk comment tree.nwk --lca A,B --dot red -o out.nwk

distance

Calculate distances between nodes or generate distance matrices.

Input:

• A valid Newick tree file.
• If the file contains multiple trees, only the first tree is processed.

Notes:

• Modes (--mode / -m):
  • root (default): distance from each node to the root. Output: Node \t Distance.
  • parent: distance from each node to its parent. Output: Node \t Distance.
  • pairwise: distance between every pair of selected nodes, including self-pairs and both (i, j) and (j, i) orderings. Output: Node1 \t Node2 \t Distance.
  • lca: distance from each node in a pair to their Lowest Common Ancestor (LCA), for all selected-node pairs. Output: Node1 \t Node2 \t Dist1 \t Dist2.
  • phylip: a PHYLIP-formatted distance matrix for the selected nodes.
• Use -I to exclude internal nodes and -L to exclude leaf nodes.
• Use -n / -l / -x to restrict reported nodes to a name, name-list file, or regex.
• When no name-based filter is given, all selected nodes (respecting -I/-L) are reported.
• --mode phylip requires all selected nodes to be named; node names cannot contain whitespace characters.

Examples:

1. Distances to root (default) necom nwk distance tree.nwk

2. Pairwise distances necom nwk distance tree.nwk --mode pairwise

3. Generate a PHYLIP matrix necom nwk distance tree.nwk --mode phylip > matrix.phy

4. Distances to parent for leaves only necom nwk distance tree.nwk --mode parent -I

5. Distance to root for selected nodes necom nwk distance tree.nwk --mode root -n Homo -n Pan

indent

Reformat a Newick tree to make its structure easier to read.

Input:

• A Newick tree file.

Notes:

• By default, prints the tree indented with two spaces (--text / -t “ “).
• Use --text / -t to customize the indentation string.
• Use --compact / -c to output the tree as a single line.
• The default output is valid Newick.
• Using non-whitespace characters for --text may produce invalid Newick.

Examples:

1. Default indentation necom nwk indent tree.nwk

2. Compact output necom nwk indent tree.nwk --compact

3. Indent with visual guides (not valid Newick) necom nwk indent tree.nwk --text ". "

label

Extract labels (names) from a Newick file.

Input:

• A Newick tree file.

Notes:

• By default, prints all non-empty labels in Newick order, one per line.
• Use --root to print only the root label.
• Use --tab / -t to print labels on a single line separated by tabs.
• Use -I to exclude internal nodes and -L to exclude leaf nodes.
• Selection options (-n, -l, -x) can be combined.
• With -D, descendants of selected internal nodes are also included.
• -M verifies that the selected nodes form a clade with at least two nodes.
• Duplicate node names may affect selection and clade checks.
• Extra columns (-c / --column):
  • dup: duplicate the node name.
  • taxid: :T= field from the comment.
  • species: :S= field from the comment.
  • full: full comment.

Examples:

1. List all labels necom nwk label tree.nwk

2. Count leaves necom nwk label tree.nwk -I | wc -l

3. List specific nodes necom nwk label tree.nwk -n Human -n Chimp

4. List labels matching a regex necom nwk label tree.nwk -x "^Homo"

5. Check clade necom nwk label tree.nwk -n Human -n Chimp -M

order

Sort the children of each node without changing the topology.

Input:

• A Newick tree file.

Notes:

• Visits every internal node and sorts its children according to the selected criterion; different modes use post-order or level-order traversals internally.
• When no sort criterion is specified, defaults to forward alphanumeric order (equivalent to --alphanumeric).
• Multiple sort options can be given in one command; they are applied in this order:
  1. --name-list
  2. --alphanumeric / --alphanumeric-rev
  3. --num-descendants / --num-descendants-rev
  4. --deladderize Each step fully reorders the children of every internal node, so later steps override earlier ones.
• --olo cannot be combined with other sort options because it computes a global optimal order from a distance matrix.
• To combine criteria as tie-breakers instead of sequential overrides, pipe multiple nwk order calls: necom nwk order tree.nwk --num-descendants | necom nwk order stdin --alphanumeric
• Sort orders:
  • --name-list: by a list of names in the file, one per line.
  • --alphanumeric (--an) / --alphanumeric-rev (--anr): by alphanumeric order of labels, or in reverse order.
  • --num-descendants (--nd) / --num-descendants-rev (--ndr): by number of descendants (ladderize), or in reverse order.
  • --deladderize (alias --dl): alternate sort direction at each level.
  • --olo <MATRIX>: optimal leaf ordering using a distance matrix.
• --olo-format controls the format of the --olo matrix: phylip (default) or pair.
• --olo expects the original data-space distance matrix, not the tree’s own path distances. Optimizing against tree-derived distances would mostly reproduce the current topology, defeating the purpose of leaf reordering.
• Entries in --name-list that are not found among the leaf names cause the command to fail with an error listing the missing names.
• The --olo matrix must cover every leaf in the tree; missing leaves cause an error. Non-finite distances are also rejected.

Examples:

1. Sort by number of descendants (ladderize) necom nwk order tree.nwk --num-descendants

2. Sort by alphanumeric order necom nwk order tree.nwk --alphanumeric

3. Sort by a list of names necom nwk order tree.nwk --name-list names.txt

4. Sort by alphanumeric order, then by number of descendants (reverse) necom nwk order tree.nwk --alphanumeric --num-descendants-rev

5. De-ladderize necom nwk order tree.nwk --deladderize

6. Optimal leaf ordering with a PHYLIP distance matrix necom nwk order tree.nwk --olo distances.phy

7. Optimal leaf ordering with a pairwise TSV matrix necom nwk order tree.nwk --olo pairs.tsv --olo-format pair

prune

Remove nodes from a Newick tree based on labels or patterns.

Input:

• A Newick tree file.

Notes:

• Target nodes can be specified by --node, --name-list, or --regex.
• With -D / --descendants, all descendants of selected internal nodes are also included in the pruning set.
• With --invert, specified nodes (along with their ancestors and descendants) are kept, and everything else is removed.
• Topology changes:
  • If a node removal leaves its parent with only one child, the parent is collapsed.
  • Internal nodes that lose all children are also removed.

Examples:

1. Remove specific nodes by name necom nwk prune input.nwk -n Homo -n Pan

2. Remove nodes using a list in a file necom nwk prune input.nwk -l remove.txt

3. Keep a clade and remove everything else (invert mode) necom nwk prune input.nwk -i -n Hominidae

rename

Rename nodes in a Newick tree.

Input:

• A Newick tree file.

Notes:

• For nodes with names, use --node.
• For unnamed internal nodes, use --lca with two comma-separated names.
• The total number of --node and --lca arguments must equal the number of --rename (-r) arguments.
• Matching order: the first N --rename values are applied to the N --node arguments in order, and the remaining --rename values are applied to the --lca arguments in order. The order in which --node, --lca, and --rename arguments appear on the command line does not affect this matching.
• This command is designed for small edits, not batch replacement. For batch replacement, use necom nwk replace or external tools such as sed or perl.

Examples:

1. Rename a named node necom nwk rename tree.nwk --node Homo --rename Human

2. Rename an internal node via LCA necom nwk rename tree.nwk --lca Homo,Pan --rename CladeX

3. Rename multiple nodes necom nwk rename tree.nwk \ --node Homo --rename Human \ --lca Homo,Pan --rename CladeX

replace

Replace node names or append annotations in a Newick file using a TSV file.

Input:

• A Newick tree file.
• A TSV file with 2 or more columns: <original_name> <replacement> [additional_annotations...].

Notes:

• The behavior of the 2nd column (<replacement>) depends on --mode:
  • label (default): replaces the node name. An empty string removes the name.
  • taxid: appends as NCBI TaxID (:T=<replacement>) in NHX.
  • species: appends as species name (:S=<replacement>) in NHX.
  • asis: appends as comments/properties. Values containing = are parsed as key=value pairs; bare values are stored as keys with empty values.
• Columns 3+ are always appended to the node’s comments/properties. Key-value pairs (e.g., color=red) are stored as properties; simple tags (e.g., highlight) are stored as keys with empty values.
• -I, --internal: skip internal nodes (don’t replace/annotate them).
• -L, --leaf: skip leaf nodes (don’t replace/annotate them).

Examples:

1. Basic renaming of nodes necom nwk replace input.nwk --replace-tsv names.tsv > output.nwk

2. Add species and color annotations necom nwk replace input.nwk --replace-tsv annotations.tsv --mode species

3. Remove node names (2nd column is empty) necom nwk replace input.nwk --replace-tsv remove.tsv

reroot

Reroot a phylogenetic tree on a specific branch or node.

Input:

• A Newick tree file.
• If the file contains multiple trees, only the first tree is processed.

Notes:

• Target selection:
  • Default (no nodes specified): reroot at the midpoint of the longest branch.
  • --node / -n: reroot on the edge leading to the LCA of the specified nodes. The specified nodes become the ingroup.
  • --lax / -l: if the LCA of specified nodes is already the root, use the unspecified nodes as the ingroup instead. Useful for defining an outgroup by exclusion.
• Operations:
  • Reroot (default): creates a bifurcating root at the target edge.
  • --deroot / -d: converts a bifurcating root into a multifurcating root by collapsing its internal children into the root. Takes priority over --node and --lax (which are ignored when --deroot is given).
• --support-as-labels / -s: treat internal node labels as support values and shift them along the rerooting path to maintain split associations.
• Topology cleanup: the original root’s parent edge is merged, and degree-2 nodes created during the process are removed.

Examples:

1. Reroot at the longest branch (default) necom nwk reroot input.nwk

2. Reroot at a specific node necom nwk reroot input.nwk -n Homo

3. Reroot at the LCA of multiple nodes necom nwk reroot input.nwk -n Homo -n Pan

4. Reroot and preserve support values necom nwk reroot input.nwk -n Homo --support-as-labels

stat

Print statistics about trees in the input.

Input:

• A Newick tree file or stdin.

Output:

• --style / -s col (default): key-value pairs.
• --style / -s line: tab-separated values with a header row.

Notes:

• Reported fields include type (cladogram/phylogram/neither), node count, leaf count, rooted status, dichotomies, leaf labels, internal labels, edges with/without length, cherries, Sackin index, and Colless index.

Examples:

1. Default statistics necom nwk stat tree.nwk

2. Output to file necom nwk stat tree.nwk -o stats.tsv

subtree

Extract a subtree (clade) rooted at the lowest common ancestor (LCA) of the selected nodes.

Input:

• A Newick tree file.

Notes:

• Node selection: use -n for exact names, -l for a name-list file, or -x for a regular expression. If no selection is provided, no output is generated.
• -M: ensure the selected nodes form a clade with at least two terminal nodes.
• --condense / -C: instead of extracting the subtree, replace it with a single node in the original tree. The new node inherits the edge length of the subtree root and receives annotations member=<count> and tri=white.
• --context / -c: extend the subtree by N levels above the LCA.

Examples:

1. Extract a subtree for two nodes necom nwk subtree tree.nwk -n Human -n Chimp

2. Extract a subtree for nodes matching a regex necom nwk subtree tree.nwk -x "^Homo"

3. Condense a clade into a single node necom nwk subtree tree.nwk -n Homo -n Pan --condense Hominini

4. Check if a group is a clade necom nwk subtree tree.nwk -n Human -n Chimp -n Gorilla -M

to-dot

Convert Newick trees to Graphviz DOT format for visualization.

Input:

• A Newick tree file.

Output:

• Graphviz DOT format.

Notes:

• Render with Graphviz tools such as dot, neato, or twopi (e.g., dot -Tpng tree.dot -o tree.png).
• Node labels come from Newick node names; edge labels come from positive branch lengths. Styling information from necom nwk comment annotations is not rendered.

Examples:

1. Convert to DOT necom nwk to-dot tree.nwk

2. Save to file necom nwk to-dot tree.nwk -o tree.dot

3. Create an image (requires Graphviz) necom nwk to-dot tree.nwk | dot -Tpng -o tree.png

to-forest

Convert a Newick tree to raw LaTeX Forest code.

Input:

• A Newick tree file.
• If the file contains multiple trees, only the first tree is processed.

Notes:

• Styles are stored in the comments of each node.
• Draws a cladogram by default.
• Use --bl to draw a phylogram with branch lengths.
• LaTeX special characters ({ } \ # $ % & ~ ^) and underscores in node names, labels, comments, and visualization attributes (dot, bar, rec, tri) are escaped or normalized for safe Forest output.

Examples:

1. Convert to Forest code necom nwk to-forest tree.nwk

2. Convert with branch lengths necom nwk to-forest tree.nwk --bl

3. Save to file necom nwk to-forest tree.nwk -o forest.tex

to-svg

Convert a Newick tree to SVG format for visualization.

Input:

• A Newick tree file.
• If the file contains multiple trees, only the first tree is processed.

Notes:

• Automatically draws a phylogram if branch lengths are present; otherwise draws a cladogram.
• Underscores (_) in names are replaced with spaces.
• Default styles match the LaTeX Forest template: grey branch lines (1 pt), black node dots (2 pt), sans-serif font.
• A scale bar is drawn in phylogram mode, using a 1×/2×/5× dynamic tick algorithm.
• --width / -w: SVG canvas width in pixels (default: 800). Must be a positive finite number.
• --vskip / -v: vertical spacing between leaf nodes in pixels (default: 20). Must be a positive finite number.

Examples:

1. Convert to SVG necom nwk to-svg tree.nwk -o tree.svg

2. Custom width and spacing necom nwk to-svg tree.nwk -w 1200 -v 30 -o tree.svg

to-tex

Convert a Newick tree to a complete LaTeX document.

Input:

• A Newick tree file.
• If the file contains multiple trees, only the first tree is processed.
• Use --forest to pass through a file that already contains Forest code.

Notes:

• Styles are stored in the comments of each node.
• Draws a cladogram by default.
• Use --bl to draw a phylogram with branch lengths.
• Underscores (_) in names, labels, comments, and visualization attributes (dot, bar, rec, tri) are replaced with spaces.
• Other LaTeX special characters ({ } \ # $ % & ~ ^) in names, labels, comments, and visualization attributes (dot, bar, rec, tri) are escaped automatically.
• Requires a LaTeX installation with fontspec, xeCJK (for East Asian characters), and the forest package. Compilation can be done with tectonic or latexmk -xelatex.
• Use --no-default-style (--style) / -s to keep the template’s original font setup instead of injecting the default Noto Sans configuration.

Examples:

1. Generate a LaTeX file necom nwk to-tex tree.nwk -o tree.tex

2. Compile with Tectonic tectonic tree.tex

3. Compile with Latexmk latexmk -xelatex tree.tex

topo

Modify tree topology by optionally removing branch lengths, comments, or labels.

Input:

• A Newick tree file.

Notes:

• By default, branch lengths and comments are removed.
• Use --bl to keep branch lengths.
• Use --comment / -c to keep comments.
• Use -I to remove internal labels.
• Use -L to remove leaf labels.

Examples:

1. Topology only (remove lengths and comments) necom nwk topo tree.nwk

2. Keep branch lengths but remove comments necom nwk topo tree.nwk --bl

3. Remove internal node labels necom nwk topo tree.nwk -I

eval

Evaluate clustering partitions and phylogenetic trees.

Input:

• eval is a command group; use one of its subcommands directly.

Notes:

• Subcommand groups:
  • Tree comparison: compare
  • Partition evaluation: partition
  • Branch support: replicate
• Run necom eval <subcommand> --help for command-specific options.
• eval compare reads from stdin if the input file is stdin.
• eval partition accepts stdin for p1 and for --other/--matrix/--tree/--coords.
• eval replicate accepts stdin for the target or replicates file (but not both at once).

Examples:

1. Show available subcommands necom eval --help

compare

Compare trees using Robinson-Foulds (RF) distance and its variants.

Input:

• One file: compares all trees in the file against each other (pairwise).
• Two files: compares each tree in the first file against each tree in the second file.
• Use "stdin" to read from standard input (only one of the two files may be stdin).

Output:

• TSV with columns Tree1, Tree2, RF_Dist, WRF_Dist, KF_Dist.
• Tree IDs are 1-based indices of the trees in the input files.

Notes:

• Metrics:
  • RF: Robinson-Foulds distance (topological difference).
  • WRF: Weighted Robinson-Foulds distance (branch length difference). Trivial splits (single-leaf branches) are excluded by default.
  • KF: Kuhner-Felsenstein (Branch Score) distance. Trivial splits are excluded by default.
• Use --include-trivial to include single-leaf splits in WRF/KF calculations.
• Single-file pairwise mode requires at least 2 trees; with fewer, the command errors out with a clear message.

Examples:

1. Compare all trees in a file necom eval compare trees.nwk

2. Compare trees between two files necom eval compare set1.nwk set2.nwk

partition

Calculate clustering evaluation metrics for partitions. Supports external comparison to a reference partition and internal evaluation using a distance matrix, tree, or coordinate matrix.

Input:

• A partition file (p1). Use "stdin" to read from standard input.
• --other / --truth, --matrix, --tree, --coords also accept "stdin".

Output:

• TSV with a header row.
• External evaluation: one row of pair-based metrics (ari, ami, homogeneity, completeness, v_measure, fmi, nmi, mi, ri, jaccard, precision, recall).
• Distance-based internal evaluation: silhouette, dunn, c_index, gamma, tau, davies_bouldin.
• Coordinate-based internal evaluation: davies_bouldin, calinski_harabasz, pbm, ball_hall, xie_beni, wemmert_gancarski.
• Batch mode (--input-format long): one row per Group, with Group as the first column.

Notes:

• Only one evaluation target may be provided per run: --other / --truth, --matrix, --tree, or --coords.
• Empty partitions are rejected in single mode and for each batch group.
• External evaluation requires the two partitions to cover exactly the same sample set.
• Internal evaluation requires every partition sample to be present in the distance source.
• With --no-singletons, singleton clusters are removed from --other before external evaluation.
• See docs/eval-partition.md for detailed metric definitions and selection guidance.

Examples:

1. External evaluation: compare result with ground truth necom eval partition result.tsv --other truth.tsv -o eval.tsv

2. Internal evaluation using a distance matrix necom eval partition result.tsv --matrix dist.phy

3. Internal evaluation using a tree file necom eval partition result.tsv --tree tree.nwk

4. Internal evaluation using coordinate vectors necom eval partition result.tsv --coords vectors.tsv

5. Batch evaluation of scan results necom eval partition partitions.tsv --input-format long --matrix dist.phy > scores.tsv

replicate

Assign support values to internal nodes of a target tree based on replicate trees.

Input:

• Target tree file (first positional argument). May contain one or more trees; each is annotated and emitted on its own line. Use "stdin" to read from standard input.
• Replicate trees file (second positional argument), e.g., from bootstrap or jackknife resampling. Use "stdin" to read from standard input.

Notes:

• Support values are written as internal node labels.
• All leaves must be named; trees with unnamed leaves are rejected (unnamed leaves would corrupt clade bitsets and produce misleading support values).
• All trees must share the same set of leaves; replicate trees are checked against the first replicate and target trees are checked against the replicate set.
• The root node is not annotated; any existing root label is preserved.
• --percent / -p: output support values as integer percentages (0–100), truncated toward zero.
• --override-root / -r: override the root node label with its support value.

Examples:

1. Attribute support values necom eval replicate target.nwk replicates.nwk

2. Output support as percentages necom eval replicate target.nwk replicates.nwk --percent

3. Override root label with support value necom eval replicate target.nwk replicates.nwk --override-root

pl

Run integrated pipelines.

Input:

• pl is a command group; use one of its subcommands directly.

Notes:

• Currently implemented subcommand:
  • condense: condense monophyletic subtrees based on a taxonomy TSV file.
• Run necom pl <subcommand> --help for command-specific options.
• Reads from stdin if input file is ‘stdin’.

Examples:

1. Show available subcommands necom pl --help

condense

Condense monophyletic subtrees whose leaves share the same taxonomic term at a selected rank into a single node.

Input:

• <infile>: Newick tree whose leaf labels match the first column of the taxonomy TSV. Use stdin for standard input.
• --taxon <taxon.tsv>: Tab-separated file without header, containing at least 2 columns:
  • Column 1: node name (must match leaf labels in the Newick file).
  • Column 2+: taxonomic terms (e.g., species, genus, family).

Output:

• Condensed Newick tree written to -o/--outfile or stdout.
• With --map, also writes condensed.tsv to the current working directory. It contains two tab-separated columns: original node name and condensed label.

Notes:

• Use --rank to select which column(s) of the taxonomy TSV to use for grouping (1-based index, default: 2).
• Multiple --rank values may be supplied to condense at multiple levels.
• Only monophyletic subtrees with the same taxonomic term are condensed; non-monophyletic groups are skipped.
• Condensed nodes are named {term}||{count}, where {count} is the number of leaves in the condensed group.
• Condensed nodes carry member=<count> and tri=white comments for visualization.

Examples:

1. Condense by species (2nd column) necom pl condense --taxon taxon.tsv tree.nwk

2. Condense by genus (3rd column) necom pl condense --taxon taxon.tsv --rank 3 tree.nwk

3. Condense by multiple ranks necom pl condense --taxon taxon.tsv --rank 2 --rank 3 tree.nwk

4. Output a mapping file alongside the condensed tree necom pl condense --taxon taxon.tsv --map tree.nwk -o condensed.nwk