rsomics-call 0.1.3

Typed alignment likelihood and small-variant calling workflow
Documentation
const INSERTION_EMISSION: f64 = 0.25;
const MISMATCH_EMISSION: f64 = 0.333_333_333_33;

pub(crate) fn score(
    reference: &[u8],
    query: &[u8],
    qualities: &[u8],
    gap_open: f64,
    gap_extension: f64,
    bandwidth: usize,
) -> Option<i32> {
    if reference.is_empty() || query.is_empty() || qualities.len() != query.len() {
        return None;
    }

    let mut bandwidth = reference.len().max(query.len()).min(bandwidth);
    bandwidth = bandwidth.max(reference.len().abs_diff(query.len()));
    let band_width = bandwidth.checked_mul(2)?.checked_add(1)?;
    let row_width = if band_width < reference.len() {
        band_width.checked_mul(3)?.checked_add(6)?
    } else {
        reference.len().checked_mul(3)?.checked_add(6)?
    };
    let rows = query.len().checked_add(1)?;
    let mut forward = vec![0.0; rows.checked_mul(row_width)?];
    let mut scales = vec![0.0; query.len().checked_add(2)?];
    let qualities = qualities
        .iter()
        .map(|&quality| 10.0f32.powf(-f32::from(quality) / 10.0))
        .collect::<Vec<_>>();

    let start_match = 1.0 / (2.0 * query.len() as f64 + 2.0);
    let start_insertion = start_match;
    let transitions = [
        (1.0 - gap_open - gap_open) * (1.0 - start_match),
        gap_open * (1.0 - start_match),
        gap_open * (1.0 - start_match),
        (1.0 - gap_extension) * (1.0 - start_insertion),
        gap_extension * (1.0 - start_insertion),
        0.0,
        1.0 - gap_extension,
        0.0,
        gap_extension,
    ];
    let begin_match = (1.0 - gap_open) / reference.len() as f64;
    let begin_insertion = gap_open / reference.len() as f64;

    let index = band_index(0, 0, bandwidth)?;
    forward[index] = 1.0;
    scales[0] = 1.0;

    let first_row = row_width;
    let end = reference.len().min(bandwidth + 1);
    let mut sum = 0.0;
    for reference_index in 1..=end {
        let emission = emission(reference[reference_index - 1], query[0], qualities[0]);
        let column = band_index(1, reference_index, bandwidth)?;
        forward[first_row + column] = emission * begin_match;
        forward[first_row + column + 1] = INSERTION_EMISSION * begin_insertion;
        sum += forward[first_row + column] + forward[first_row + column + 1];
    }
    scales[1] = sum;

    for query_index in 2..=query.len() {
        let row = query_index * row_width;
        let previous_row = (query_index - 1) * row_width;
        let begin = 1usize.max(query_index.saturating_sub(bandwidth));
        let end = reference.len().min(query_index.saturating_add(bandwidth));
        let scale = 1.0 / scales[query_index - 1];
        let mut sum = 0.0;

        for reference_index in begin..=end {
            let column = band_index(query_index, reference_index, bandwidth)?;
            let diagonal = band_index(query_index - 1, reference_index - 1, bandwidth)?;
            let vertical = band_index(query_index - 1, reference_index, bandwidth)?;
            let horizontal = band_index(query_index, reference_index - 1, bandwidth)?;
            let emission = emission(
                reference[reference_index - 1],
                query[query_index - 1],
                qualities[query_index - 1],
            );
            let matched = emission
                * (transitions[0] * scale * forward[previous_row + diagonal]
                    + transitions[3] * scale * forward[previous_row + diagonal + 1]
                    + transitions[6] * scale * forward[previous_row + diagonal + 2]);
            let inserted = INSERTION_EMISSION
                * (transitions[1] * scale * forward[previous_row + vertical]
                    + transitions[4] * scale * forward[previous_row + vertical + 1]);
            let deleted = transitions[2] * forward[row + horizontal]
                + transitions[8] * forward[row + horizontal + 2];
            forward[row + column] = matched;
            forward[row + column + 1] = inserted;
            forward[row + column + 2] = deleted;
            sum += matched + inserted + deleted;
        }
        scales[query_index] = sum;
    }

    let last_row = query.len() * row_width;
    let scale = 1.0 / scales[query.len()];
    let mut terminal = 0.0;
    for reference_index in 1..=reference.len() {
        let Some(column) = band_index(query.len(), reference_index, bandwidth) else {
            continue;
        };
        if column < 3 || column >= row_width {
            continue;
        }
        terminal += scale * forward[last_row + column] * start_match
            + scale * forward[last_row + column + 1] * start_insertion;
    }
    scales[query.len() + 1] = terminal;

    let mut product = 1.0;
    let mut phred = 0.0;
    for scale in scales {
        product *= scale;
        if product < 1e-100 {
            phred += -4.343 * product.ln();
            product = 1.0;
        }
    }
    phred += -4.343 * (product * reference.len() as f64 * query.len() as f64).ln();
    if phred.is_finite() && phred >= f64::from(i32::MIN) && phred <= f64::from(i32::MAX) {
        Some((phred + 0.499) as i32)
    } else {
        None
    }
}

fn emission(reference: u8, query: u8, quality: f32) -> f64 {
    if reference > 3 || query > 3 {
        1.0
    } else if reference == query {
        1.0 - f64::from(quality)
    } else {
        f64::from(quality) * MISMATCH_EMISSION
    }
}

fn band_index(query_index: usize, reference_index: usize, bandwidth: usize) -> Option<usize> {
    let start = query_index.saturating_sub(bandwidth);
    reference_index
        .checked_add(1)?
        .checked_sub(start)?
        .checked_mul(3)
}

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

    #[test]
    fn matches_htslib_1_24_likelihood_scores() {
        let reference = [0, 1, 2, 3, 0, 1, 2, 3];
        let exact = [0, 1, 2, 3, 0, 1, 2, 3];
        let insertion = [0, 1, 2, 3, 3, 0, 1, 2, 3];
        let deletion = [0, 1, 2, 0, 1, 2, 3];
        let mismatch = [0, 1, 2, 3, 3, 1, 2, 3];
        let ambiguous = [0, 1, 4, 3, 0, 1, 2, 3];

        assert_eq!(score(&reference, &exact, &[30; 8], 1e-4, 1e-2, 10), Some(5));
        assert_eq!(
            score(&reference, &insertion, &[30; 9], 1e-4, 1e-2, 4),
            Some(48)
        );
        assert_eq!(
            score(&reference, &deletion, &[30; 7], 1e-4, 1e-2, 4),
            Some(45)
        );
        assert_eq!(
            score(&reference, &mismatch, &[30; 8], 1e-4, 1e-2, 10),
            Some(40)
        );
        assert_eq!(
            score(&reference, &ambiguous, &[30; 8], 1e-4, 1e-2, 10),
            Some(5)
        );
    }
}