speedytree 0.1.0

Canonical and RapidNJ implementations of Neighbor-joining in Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

use crate::{
    distances::DistanceMatrix, naive_nj::DataNaiveNJ, rapid_nj::DataRapidNJ, ResultBox, Tree,
};

/// This approach is a hybrid between the naive neighbor joining and the rapid neighbor joining.
/// If `naive_iters` is greater than n, then this function calls `naive_neighbor_joining` instead.
/// If `naive_iters` is less than 4, then this function calls `rapid_nj` instead.
/// Arguments:
/// * `dist` - Distance matrix
/// * `naive_iters` - Number of iterations to use the naive neighbor joining algorithm
///
/// Returns:
/// * `Ok(Tree)` - A phylogenetic tree
/// * `Err(Box<dyn error::Error>)` - An error
pub fn neighbor_joining(
    dist: DistanceMatrix,
    naive_iters: usize,
    chunk_size: usize,
) -> ResultBox<Tree> {
    if dist.size() < 4 || naive_iters >= dist.size() {
        return crate::naive_nj::canonical_neighbor_joining(dist);
    }
    if naive_iters < 4 {
        return crate::rapid_nj::rapid_nj(dist, chunk_size);
    }
    let mut q = crate::rapid_nj::QMatrix::from(&dist);
    let mut t = crate::rapid_nj::PhyloTree::build(&dist.names);
    q.set_chunk_size(chunk_size);
    while q.n_leaves() > naive_iters {
        let (i, j) = q.find_neighbors();
        let (dist_ui, dist_uj) = q.new_node_distances(i, j);
        t.merge_neighbors(i, j, dist_ui, dist_uj);
        q.update(i, j);
    }
    // Convert to the inner data structure of the naive neighbor joining
    let data = DataNaiveNJ::from(DataRapidNJ::new(q, t));
    let mut q = data.qmatrix;
    let mut t = data.phylo_tree;
    while q.n_leaves() > 3 {
        let (i, j) = q.find_neighbors();
        let (dist_ui, dist_uj) = q.new_node_distances(i, j);
        t.merge_neighbors(i, j, dist_ui, dist_uj);
        q.update_distance_matrix(i, j);
    }
    Ok(crate::naive_nj::terminate_nj(t, q))
}