Function bio::alignment::sparse::sdpkpp

pub fn sdpkpp(
    matches: &[(u32, u32)],
    k: usize,
    match_score: u32,
    gap_open: i32,
    gap_extend: i32
) -> SparseAlignmentResult

Sparse DP routine generalizing LCSk++ method above to penalize alignment gaps. A gap is an unknown combination of mismatch, insertion and deletions, and incurs a penalty of gap_open + d * gap_extend, where d is the distance along the diagonal of the gap.

Arguments

• matches - a vector of tuples indicating the (string1 position, string2 position) kmer matches between the strings
• k - the kmer length used for matching
• match_score - reward for each matched base
• gap_open - score of opening a gap, including a mismatch gap. Must be negative.
• gap_extend - score for extending a gap along the diagonal. Must be negative.

Return value

The method returns a SparseAlignmentResult struct with the following fields:

• path is the SDP path, represented as vector of indices into the input matches vector.
• score is the score of the path, which is the number of bases covered by the matched kmers.
• dp_vector is the full DP vector, which can generally be ignored. (It may be useful for testing purposes).