abd-clam 0.21.3

Clustered Learning of Approximate Manifolds
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

//! This will soon be moved into the `distances` crate.

pub(crate) mod alignment_helpers;

use distances::Number;

/// Calculate the edit distance between two strings using Needleman-Wunsch table.
/// This function is only accurate with a scoring scheme for which all penalties
/// are non-negative.
///
/// * [Demo](https://bioboot.github.io/bimm143_W20/class-material/nw/)
/// * [Wikipedia](https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm)
///
/// # Arguments:
///
/// * `x`: unaligned sequence represented as a `String`
/// * `y`: unaligned sequence represented as a `String`
#[must_use]
pub fn nw_distance<U: Number>(x: &str, y: &str) -> U {
    let table = alignment_helpers::compute_table(x, y);
    let edit_distance: usize = table[table.len() - 1][table[0].len() - 1].0;

    U::from(edit_distance)
}

/// Determine the set of edits needed to turn one unaligned sequence into another,
/// as well as the edit distance between the two sequences.
///
/// Contrast to `with_edits_iterative`, which uses an iterative, as
/// opposed to recursive, traceback function
///
/// For now, in cases where there exist ties for the shortest edit distance, we only
/// return one alignment.
///
/// # Arguments:
///
/// * `x`: unaligned sequence represented as a `String`
/// * `y`: unaligned sequence represented as a `String`
#[must_use]
pub fn with_edits_recursive<U: Number>(x: &str, y: &str) -> ([Vec<alignment_helpers::Edit>; 2], U) {
    let table = alignment_helpers::compute_table(x, y);
    let (aligned_x, aligned_y) = alignment_helpers::trace_back_recursive(&table, (x, y));

    let edit_x_into_y = alignment_helpers::alignment_to_edits(&aligned_x, &aligned_y);
    let edit_y_into_x = alignment_helpers::alignment_to_edits(&aligned_y, &aligned_x);

    let edit_distance: usize = table[table.len() - 1][table[0].len() - 1].0;

    ([edit_x_into_y, edit_y_into_x], U::from(edit_distance))
}

/// Determine the set of edits needed to turn one unaligned sequence into another,
/// as well as the edit distance between the two sequences.
///
/// Contrast to `with_edits_recursive`, which uses a recursive, as
/// opposed to iterative, traceback function
///
/// For now, in cases where there exist ties for the shortest edit distance, we only
/// return one alignment.
///
/// # Arguments:
///
/// * `x`: unaligned sequence represented as a `String`
/// * `y`: unaligned sequence represented as a `String`
#[must_use]
pub fn with_edits_iterative<U: Number>(x: &str, y: &str) -> ([Vec<alignment_helpers::Edit>; 2], U) {
    let table = alignment_helpers::compute_table(x, y);
    let (aligned_x, aligned_y) = alignment_helpers::trace_back_iterative(&table, (x, y));

    let edit_x_into_y = alignment_helpers::alignment_to_edits(&aligned_x, &aligned_y);
    let edit_y_into_x = alignment_helpers::alignment_to_edits(&aligned_y, &aligned_x);

    let edit_distance: usize = table[table.len() - 1][table[0].len() - 1].0;

    ([edit_x_into_y, edit_y_into_x], U::from(edit_distance))
}

#[cfg(test)]
mod tests {
    use super::nw_distance;

    #[test]
    fn test_needleman_wunsch() {
        let x = "NAJIBEATSPEPPERS".to_string();
        let y = "NAJIBPEPPERSEATS".to_string();
        let d: u8 = nw_distance(&x, &y);
        assert_eq!(d, 8);

        let x = "NOTGUILTY".to_string();
        let y = "NOTGUILTY".to_string();
        let d: u8 = nw_distance(&x, &y);
        assert_eq!(d, 0);
    }
}