whittle 1.0.0

Coordinate-consistent trimming of long-read uBAM and tagged FASTQ
Documentation
//! Support of a candidate among read-end windows, sequence identity between
//! candidates, and catalog naming of discovered sequences.

use super::*;

/// Requires supporting alignments to concentrate near the physical read end.
pub(super) fn terminal_support(
    seq: &[u8],
    windows: &[&[u8]],
    end: End,
    edits: usize,
) -> (usize, usize) {
    let mut searcher = crate::adapter::search::new_searcher_fwd();
    let mut best = vec![None; windows.len()];
    for hit in searcher.search_texts(seq, windows, edits) {
        let distance = match end {
            End::Five => hit.text_start,
            End::Three => windows[hit.text_idx].len() - hit.text_end,
        };
        let key = (hit.cost, distance);
        let entry = &mut best[hit.text_idx];
        if entry.is_none_or(|old| key < old) {
            *entry = Some(key);
        }
    }
    let present = best.iter().filter(|hit| hit.is_some()).count();
    let anchored = best
        .iter()
        .flatten()
        .filter(|(_, distance)| *distance <= ANCHOR_SLACK)
        .count();
    (present, anchored)
}

/// Counts the distinct `windows` with at least one forward approximate
/// occurrence of `pattern` within `max_edits`. Each window counts at most once,
/// however often `pattern` occurs in it. `searcher` must be forward-only (see
/// `new_searcher_fwd`) so reverse-complement occurrences do not inflate the
/// count. Callers provide an already bounded window sample.
pub(super) fn windows_containing(
    searcher: &mut AmbiguousSearcher,
    pattern: &[u8],
    windows: &[&[u8]],
    max_edits: usize,
) -> u32 {
    let mut seen = vec![false; windows.len()];
    crate::adapter::search::for_each_hit_in_texts(
        searcher,
        pattern,
        windows,
        max_edits,
        |index, _| seen[index] = true,
    );
    seen.into_iter().filter(|&present| present).count() as u32
}

/// Returns, per window, whether `pattern` occurs within `max_edits`.
pub(super) fn windows_with(
    searcher: &mut AmbiguousSearcher,
    pattern: &[u8],
    windows: &[&[u8]],
    max_edits: usize,
) -> Vec<bool> {
    let mut seen = vec![false; windows.len()];
    crate::adapter::search::for_each_hit_in_texts(
        searcher,
        pattern,
        windows,
        max_edits,
        |index, _| seen[index] = true,
    );
    seen
}

/// Marks the windows that `pattern` covers: a hit within `max_edits` whose
/// alignment leaves fewer than `MIN_OVERLAP` bases to clip (`refine`). A hit
/// that aligns part of the pattern and pays for the rest in edits, as a
/// candidate sharing only an adapter with another layer does, covers nothing.
pub(super) fn windows_covered(
    searcher: &mut AmbiguousSearcher,
    pattern: &[u8],
    windows: &[&[u8]],
    max_edits: usize,
) -> Vec<bool> {
    let mut seen = vec![false; windows.len()];
    crate::adapter::search::for_each_hit_in_texts(
        searcher,
        pattern,
        windows,
        max_edits,
        |index, hit| {
            if hit.clip_start + hit.clip_end < crate::adapter::MIN_OVERLAP {
                seen[index] = true;
            }
        },
    );
    seen
}

/// Returns whether `a` and `b` are the same adapter within `error_rate`: an
/// approximate occurrence of the shorter in the longer on either strand (the
/// both-strand searcher covers the reverse-complement case).
pub(super) fn same_adapter(a: &[u8], b: &[u8], error_rate: f64) -> bool {
    let (short, long) = if a.len() <= b.len() { (a, b) } else { (b, a) };
    if short.len() < MIN_PATTERN_LEN {
        return short == long;
    }
    let k = edit_budget(error_rate, short.len());
    let mut s = new_ambiguous_searcher();
    !hits(&mut s, short, long, k).is_empty()
}

/// Returns the best catalog matches for `seq` as `(name, percent_identity)`,
/// sorted by identity descending, at most three, and only at or above
/// `NAME_IDENTITY_MIN`. The result annotates an inferred adapter with the
/// catalog entry it corresponds to.
pub(super) fn name_against(seq: &[u8], refs: &[Adapter], error_rate: f64) -> Vec<(String, f32)> {
    let mut s = new_ambiguous_searcher();
    let mut named: Vec<(String, f32)> = Vec::new();
    // A barcode construct's `N` block matches any sequence and names nothing.
    for r in refs.iter().filter(|r| !crate::adapter::is_construct(r)) {
        let (short, long) = if seq.len() <= r.seq.len() {
            (seq, r.seq.as_slice())
        } else {
            (r.seq.as_slice(), seq)
        };
        if short.len() < MIN_PATTERN_LEN {
            continue;
        }
        let k = edit_budget(error_rate, short.len());
        if let Some(h) = hits(&mut s, short, long, k)
            .into_iter()
            .min_by_key(|h| h.cost)
        {
            let pct = 100.0 * (1.0 - h.cost as f32 / short.len() as f32);
            if pct >= NAME_IDENTITY_MIN {
                named.push((r.name.clone(), pct));
            }
        }
    }
    named.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap().then(a.0.cmp(&b.0)));
    named.truncate(3);
    named
}

/// Samples at most `cap` windows deterministically, spread across the whole
/// slice by stride rather than taken from its start, so the recount and
/// support frame in `assemble` is not order-biased. Returns every window in
/// order when `windows.len() <= cap`.
pub(super) fn stride_sample<'a>(windows: &[&'a [u8]], cap: usize) -> Vec<&'a [u8]> {
    let step = windows.len().div_ceil(cap.max(1)).max(1);
    windows.iter().step_by(step).copied().collect()
}

/// Returns whether two candidates reconstruct one family: the same adapter
/// within the error budget, or reconstructions whose longest common
/// substring covers `FAMILY_OVERLAP_PERCENT` of the shorter, as remnants of
/// one adapter that differ in length do.
pub(super) fn same_family(a: &[u8], b: &[u8], error_rate: f64) -> bool {
    same_adapter(a, b, error_rate)
        || shared_substring(a, b) * 100 >= a.len().min(b.len()) * FAMILY_OVERLAP_PERCENT
}

/// Returns the form in which the other read end holds the family of `seq`,
/// accepted at `end`, when that end's form stops at a different base on the
/// insert side, with its support. The form grows from the longest candidate
/// of the other end, in `candidates` as `(sequence, support, weight, end)`,
/// that holds at least `KMER_K` bases and half of `seq` and whose reverse
/// complement aligns inside `seq` within its edit budget, short of the inner
/// end of `seq`. Erosion at the other physical end shortens that candidate
/// on its outer side, so the form extends outward with the bases `seq` holds
/// there for as long as most of the `other_windows` that hold the candidate,
/// and at least `MIN_SUPPORT_WINDOWS` of them, carry the same base. A
/// candidate that differs only on its outer side, as an eroded read end
/// does, is covered by `seq` and yields no form; a shorter one is a fragment
/// of a layer.
pub(super) fn other_end_form(
    seq: &[u8],
    end: End,
    candidates: &[(Vec<u8>, f64, u64, End)],
    other_windows: &[&[u8]],
    error_rate: f64,
) -> Option<(Vec<u8>, f64)> {
    let mut searcher = crate::adapter::search::new_searcher_fwd();
    let (other, support, oriented_hit) = candidates
        .iter()
        .filter(|(other, _, _, other_end)| {
            *other_end != end
                && other.len() >= KMER_K
                && other.len() * 2 >= seq.len()
                && other.len() < seq.len()
        })
        .filter_map(|(other, support, weight, _)| {
            let oriented = crate::adapter::reverse_complement(other);
            let hit = searcher
                .search(&oriented, &seq, edit_budget(error_rate, other.len()))
                .into_iter()
                .min_by_key(|m| (m.cost, m.text_start))?;
            let short = match end {
                End::Five => hit.text_end < seq.len(),
                End::Three => hit.text_start > 0,
            };
            short.then_some((other, *support, *weight, hit))
        })
        .max_by(|a, b| {
            a.0.len()
                .cmp(&b.0.len())
                .then(a.2.cmp(&b.2))
                .then(b.0.cmp(a.0))
        })
        .map(|(other, support, _, hit)| (other, support, hit))?;
    // The bases of `seq` outward of the candidate, as the other end reads
    // them: complements of the bases before the aligned part of `seq` for a
    // 5' `seq`, after it for a 3' one.
    let outward: Vec<u8> = match end {
        End::Five => seq[..oriented_hit.text_start]
            .iter()
            .rev()
            .map(|&b| crate::adapter::reverse_complement(&[b])[0])
            .collect(),
        End::Three => seq[oriented_hit.text_end..]
            .iter()
            .map(|&b| crate::adapter::reverse_complement(&[b])[0])
            .collect(),
    };
    let mut best: Vec<Option<(i32, usize, usize)>> = vec![None; other_windows.len()];
    for hit in searcher.search_texts(other, other_windows, edit_budget(error_rate, other.len())) {
        let entry = &mut best[hit.text_idx];
        if entry.is_none_or(|(cost, _, _)| hit.cost < cost) {
            *entry = Some((hit.cost, hit.text_start, hit.text_end));
        }
    }
    // The other end reads its form toward the physical 3' end for a 5'
    // `seq`, and toward the physical 5' end for a 3' one.
    let mut extension = Vec::new();
    for (step, &expected) in outward.iter().enumerate() {
        let (mut carried, mut held) = (0, 0);
        for (window, hit) in other_windows.iter().zip(&best) {
            let Some((_, start, stop)) = *hit else {
                continue;
            };
            let base = match end {
                End::Five => window.get(stop + step),
                End::Three => start.checked_sub(step + 1).and_then(|i| window.get(i)),
            };
            if let Some(&base) = base {
                held += 1;
                carried += usize::from(base.to_ascii_uppercase() == expected);
            }
        }
        if carried < MIN_SUPPORT_WINDOWS || carried * 2 <= held {
            break;
        }
        extension.push(expected);
    }
    let form = match end {
        End::Five => [other.as_slice(), &extension].concat(),
        End::Three => extension.iter().rev().chain(other).copied().collect(),
    };
    Some((form, support))
}

/// Bases by which a trim may stop short of a candidate's inner edge and
/// still count as trimming it, for alignment differences at the edge.
const FORM_TRIM_SLACK: usize = 3;

/// Returns the candidate of the other read end, with its support and end,
/// that the family of `seq`, accepted at `end`, does not trim: the longest
/// candidate of the other end, in `candidates` as `(sequence, support,
/// weight, end)`, of at least `KMER_K` bases that shares the family
/// (`same_family`), in whose `other_windows` a trim with `seq` alone stops
/// more than `FORM_TRIM_SLACK` bases short of the candidate's inner edge in
/// at least half of the windows that hold it. The other end then reads the
/// family in a form of its own, with inner or outer bases that `seq` lacks,
/// as a hairpin adapter read on the same strand at both ends is.
pub(super) fn untrimmed_other_end(
    seq: &[u8],
    end: End,
    candidates: &[(Vec<u8>, f64, u64, End)],
    other_windows: &[&[u8]],
    base: &AdapterConfig,
) -> Option<(Vec<u8>, f64, End)> {
    let family = AdapterConfig {
        adapters: vec![Adapter {
            name: "family".into(),
            seq: seq.to_vec(),
            role: Role::Adapter,
        }],
        error_rate: base.error_rate,
        end_size: base.end_size,
        split: false,
        min_piece: 1,
        candidate_index: std::sync::OnceLock::new(),
        amplicon: false,
    };
    let mut searcher = crate::adapter::search::new_searcher_fwd();
    candidates
        .iter()
        .filter(|(other, _, _, other_end)| {
            *other_end != end && other.len() >= KMER_K && same_family(seq, other, base.error_rate)
        })
        .filter(|(other, _, _, other_end)| {
            let mut best: Vec<Option<(i32, usize, usize)>> = vec![None; other_windows.len()];
            for hit in searcher.search_texts(
                other,
                other_windows,
                edit_budget(base.error_rate, other.len()),
            ) {
                let entry = &mut best[hit.text_idx];
                if entry.is_none_or(|(cost, _, _)| hit.cost < cost) {
                    *entry = Some((hit.cost, hit.text_start, hit.text_end));
                }
            }
            let (mut held, mut untrimmed) = (0, 0);
            for (window, hit) in other_windows.iter().zip(&best) {
                let Some((_, start, stop)) = *hit else {
                    continue;
                };
                held += 1;
                let kept = crate::adapter::adapter_segments(window, &family);
                untrimmed += usize::from(match other_end {
                    End::Five => kept
                        .first()
                        .is_some_and(|&(first, _)| first + FORM_TRIM_SLACK < stop),
                    End::Three => kept
                        .last()
                        .is_some_and(|&(_, last)| last > start + FORM_TRIM_SLACK),
                });
            }
            held >= MIN_SUPPORT_WINDOWS && untrimmed * 2 >= held
        })
        .max_by(|a, b| {
            a.0.len()
                .cmp(&b.0.len())
                .then(a.2.cmp(&b.2))
                .then(b.0.cmp(&a.0))
        })
        .map(|(other, support, _, other_end)| (other.clone(), *support, *other_end))
}

/// Returns whether the shorter of two candidates is a fragment of the
/// longer: one family by `same_family`, with less than `MIN_PATTERN_LEN` of
/// the shorter outside their longest common substring, as an end of the
/// longer extended by a few bases the assembly could not support is.
pub(super) fn fragment_of(a: &[u8], b: &[u8], error_rate: f64) -> bool {
    let short = a.len().min(b.len());
    same_adapter(a, b, error_rate) || {
        let shared = shared_substring(a, b);
        shared * 100 >= short * FAMILY_OVERLAP_PERCENT && short - shared < MIN_PATTERN_LEN
    }
}

/// Length of the longest substring `a` shares with `b` on either strand.
pub(super) fn shared_substring(a: &[u8], b: &[u8]) -> usize {
    longest_common_substring(a, b).max(longest_common_substring(
        &crate::adapter::reverse_complement(a),
        b,
    ))
}

/// Length of the longest common substring of `a` and `b`.
pub(super) fn longest_common_substring(a: &[u8], b: &[u8]) -> usize {
    let mut longest = 0;
    let mut previous = vec![0usize; b.len() + 1];
    for &x in a {
        let mut current = vec![0usize; b.len() + 1];
        for (j, &y) in b.iter().enumerate() {
            if x == y {
                current[j + 1] = previous[j] + 1;
                longest = longest.max(current[j + 1]);
            }
        }
        previous = current;
    }
    longest
}