Dataset Information

Scaling neighbor joining to one million taxa with dynamic and heuristic neighbor joining.

ABSTRACT:

Motivation

The neighbor-joining (NJ) algorithm is a widely used method to perform iterative clustering and forms the basis for phylogenetic reconstruction in several bioinformatic pipelines. Although NJ is considered to be a computationally efficient algorithm, it does not scale well for datasets exceeding several thousand taxa (>100 000). Optimizations to the canonical NJ algorithm have been proposed; these optimizations are, however, achieved through approximations or extensive memory usage, which is not feasible for large datasets.

Results

In this article, two new algorithms, dynamic neighbor joining (DNJ) and heuristic neighbor joining (HNJ), are presented, which optimize the canonical NJ method to scale to millions of taxa without increasing the memory requirements. Both DNJ and HNJ outperform the current gold standard methods to construct NJ trees, while DNJ is guaranteed to produce exact NJ trees.

Availability and implementation

https://bitbucket.org/genomicepidemiology/ccphylo.git.

Supplementary information

Supplementary data are available at Bioinformatics online.

SUBMITTER: Clausen PTLC

PROVIDER: S-EPMC9805563 | biostudies-literature | 2023 Jan

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Scaling neighbor joining to one million taxa with dynamic and heuristic neighbor joining.

Clausen Philip T L C PTLC

Bioinformatics (Oxford, England) 20230101 1

<h4>Motivation</h4>The neighbor-joining (NJ) algorithm is a widely used method to perform iterative clustering and forms the basis for phylogenetic reconstruction in several bioinformatic pipelines. Although NJ is considered to be a computationally efficient algorithm, it does not scale well for datasets exceeding several thousand taxa (>100 000). Optimizations to the canonical NJ algorithm have been proposed; these optimizations are, however, achieved through approximations or extensive memory ...[more]

PMID: 36453849

Similar Datasets

Project description:The neighbor-joining algorithm for phylogenetic inference (NJ) has been seen to have three specific properties when applied to distance matrices that contain an admixed taxon: (1) antecedence of clustering, in which the admixed taxon agglomerates with one of its source taxa before the two source taxa agglomerate with each other; (2) intermediacy of distances, in which the distance on an inferred NJ tree between an admixed taxon and either of its source taxa is smaller than the distance between the two source taxa; and (3) intermediacy of path lengths, in which the number of edges separating the admixed taxon and either of its source taxa is less than or equal to the number of edges between the source taxa. We examine the behavior of neighbor-joining on distance matrices containing an admixed group, investigating the occurrence of antecedence of clustering, intermediacy of distances, and intermediacy of path lengths. We first mathematically predict the frequency with which the properties are satisfied for a labeled unrooted binary tree selected uniformly at random in the absence of admixture. We then introduce a taxon constructed by a linear admixture of distances from two source taxa, examining three admixture scenarios by simulation: a model in which distance matrices are chosen at random, a model in which an admixed taxon is added to a set of taxa that reflect treelike evolution, and a model that introduces a perturbation of the treelike scenario. In contrast to previous conjectures, we observe that the three properties are sometimes violated by distance matrices that include an admixed taxon. However, we also find that they are satisfied more often than is expected by chance when the distance matrix contains an admixed taxon, especially when evolution among the non-admixed taxa is treelike. The results contribute to a deeper understanding of the nature of evolutionary trees constructed from data that do not necessarily reflect a treelike evolutionary process.

Project description:Stomata are involved in transpiration and CO2 uptake by mediating gas exchange between internal plant tissues and the atmosphere. The capacity for gas exchange depends on stomatal density (SD), stomatal size, and pore dimensions. Most published work on stomatal quantification has assumed that stomatal distribution and stomatal density are spatially homogeneous across the leaf, but this assumption has been seldom tested. We selected 32 leaves from a Photinia hybrid, Photinia × fraseri 'Red Robin', and one of its parents, P. serratifolia. For each leaf, the leaf surface was divided into three or four equidistant layers along the apical-basal axis, and, in each layer, two positions, one closer to the midrib and the other closer to the leaf margin, were further selected. We calculated SD and mean nearest neighbor distance (MNND) for each lamina section and tested the scaling relationship between SD and MNND of the sampled stomatal centers using reduced major axis protocols. In addition, we calculated the stomatal aggregation index (SAI) for each lamina section to examine the spatial arrangement of stomata at the given size of field of view of 1.2 mm × 0.9 mm. We observed that SD decreased from the lamina apex towards the base for central lamina areas but varied little at leaf margins. An inverse scaling relationship between SD and MNND was observed for both species. This relationship could be used for SD estimation using the rapidly estimated trait, MNND. SAI did not vary significantly throughout leaf lamina, and the numerical values of SAI for all fields of view were greater than one, which indicates significant spatial repulsion between stomata. The study suggests that SD varies across leaf lamina to fine-tune plant water use and maximize carbon gain. However, spatial structures of stomata from different lamina sections exhibit similar patterns (i.e., spatial inhibition between stomata at small scales), probably due to hierarchical leaf vein patterns.

Dataset Information

Scaling neighbor joining to one million taxa with dynamic and heuristic neighbor joining.

Motivation

Results

Availability and implementation

Supplementary information

Publications

Scaling neighbor joining to one million taxa with dynamic and heuristic neighbor joining.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets