mini_myers 0.1.0

🤏 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};

let queries = vec![b"ATG".to_vec(), b"TTG".to_vec()];
let transposed = TQueries::new(&queries);
let target = b"CCCTCGCCCCCCATGCCCCC";
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};

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 result = mini_search_with_positions(&transposed, target, 4, &mut results, None);
println!("Result: {:?}", result); 
// Result: [MatchInfo { query_idx: 1, cost: 1, pos: 5 }, MatchInfo { query_idx: 0, cost: 1, pos: 13 }, MatchInfo { query_idx: 0, cost: 0, pos: 14 }, MatchInfo { query_idx: 1, cost: 1, pos: 14 }, MatchInfo { query_idx: 0, cost: 1, pos: 15 }]

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, mini_search_with_positions does return the match locations similar to sassy though without traceback. Here we have a batch of 32 which is ideal for mini_myers as well.

Searching for 32 queries in a 100K DNA string with k=4.

Run the bench using cargo bench --bench sassy.