mini_myers 0.1.2

🤏 Mini Myers

SIMD Myers implementation to "check" whether "batches" of short patterns (<=32nt) are present in a longer text with at most k edits.

Mainly for Barbell as a faster pre-filter before running sassy, so most likely you are looking for sassy instead.

When to use

• Short queries (<=32)
• Search for multiple of 8 queries

What it does

We compare each character of the queries against a single text character at the time using SIMD. Then we track the lowest cost we see along the entire text and report the cost when below the cut-off k, or -1 if above k for mini_search, at a ~5% overhead we can also track the positions in mini_search_positions.

How to use:

Without position tracking

This will just return the lowest edits found (below k) for each query.

use mini_myers::{TQueries, mini_search, MyersSearchState};

let queries = vec![b"ATG".to_vec(), b"TTG".to_vec()];
let transposed = TQueries::new(&queries);
let target = b"CCCTCGCCCCCCATGCCCCC";
let mut state = MyersSearchState::new(); // to re-use allocs
let result = mini_search(&transposed, target, 4, None);
println!("Result: {:?}", result); 
// [0,1] (ATG = 0 edits, TTG = 1 edit)

With position tracking

use mini_myers::{TQueries, mini_search_with_positions, MyersSearchState};

let queries = vec![b"ATG".to_vec(), b"TTG".to_vec()];
let transposed = TQueries::new(&queries);
let target = b"CCCTCGCCCCCCATGCCCCC";
let mut results = Vec::new();
let mut state = MyersSearchState::new(); // to re-use allocs
mini_search_with_positions(&mut state, &transposed, target, 1, None, &mut results);
println!("Result: {:?}", results);
// Result: [MatchInfo { query_idx: 1, cost: 1, pos: 5 } ...

This returns all positions, which is not ideal perhaps, sassy returns the local minima position.

With "overhang" enabled

Like in sassy mini_myers can apply a reduced penalty for characters "hanging over" the target sequence, i.e.:

    q: AAACCC
          |||
    t:    CCCGGGGGGGGGGGGGG

You can enable overhang by changing None in the above commands to Some(overhang_cost), i.e. Some(0.5):

let result = mini_search_with_positions(&transposed, target, 4, &mut results, Some(0.5));

In the example above, this would give a cost of 3 * 0.5 = 1.5

Benchmark

Note that mini_myers and sassy are not directly comparable. mini_seaerch just tells us if something is present below k, and mini_search_with_positions does return the match locations similar to sassy but without traceback and local minima scan. Here we search for 192 sequences, a multiple of 8, which is ideal for mini_myers as well.

Run the bench using cargo bench --bench sassy, now has mini_search_with_positions but you can replace the call with mini_search to bench without positions.