[−][src]Crate rust_lapper
(Docs from nim-lapper, by Brent Pendersen) This module provides a simple data-structure for fast interval searches.
0 1 2 3 4 5 6 7 8 9 10 11
(0,10]X X X X X X X X X X
(2,5] X X X
(3,8] X X X X X
(3,8] X X X X X
(3,8] X X X X X
(3,8] X X X X X
(5,9] X X X X
(8,11] X X X
Query: (8, 11]
Answer: ((0,10], (5,9], (8,11])
The main methods are find
and seek
where the latter uses a cursor and is very fast for
cases when the queries are sorted. This is another innovation in this library that allows an
additional ~50% speed improvement when consecutive queries are known to be in sort order.
The overlap function for this assumes a zero based genomic coordinate system. So [start, stop) is not inclusive of the stop position for neither the queries, nor the Intervals.
Lapper does not use an interval tree, instead, it operates on the assumtion that most intervals are of similar length; or, more exactly, that the longest interval in the set is not long compred to the average distance between intervals.
For cases where this holds true (as it often does with genomic data), we can sort by start and use binary search on the starts, accounting for the length of the longest interval. The advantage of this approach is simplicity of implementation and speed. In realistic tests queries returning the overlapping intervals are 1000 times faster than brute force and queries that merely check for the overlaps are > 5000 times faster.
On any dataset where that is not the case, It is suggested that you set the {find,seek}_skip
methods. This allows the lapper to redo its binary search if no intervals have been found in the
last N intervals seen, as would happen in a scenario with very long intervals. An example of this
can be seen in the diagram above. Without setting max_misses, every interval between the first and
the last one would need to be tested. By seeting max_misses to 2, after (2, 5] and the first (3, 8]
miss, the sublist that hasn't been tested yet would be binar searched to find a better offset, and
skip the other 3 (3, 8], and head strait to (5, 9]. You should benchmark this for your data. It
can cause a best case dataset to be slower, as just iterating over misses is still often
faster than redoing a binary search.
A better alternative, if it's possible in your scenario, is to use merge_overlaps first, and then use the normal find and seek methods.
Examples
use rust_lapper::{Interval, Lapper}; use std::cmp; type Iv = Interval<u32>; // create some fake data let data: Vec<Iv> = (0..20).step_by(5).map(|x| Iv{start: x, stop: x + 2, val: 0}).collect(); println!("{:#?}", data); // make lapper structure let laps = Lapper::new(data); assert_eq!(laps.find(6, 11).next(), Some(&Iv{start: 5, stop: 7, val: 0})); // Demonstration of seek function. By passing in the &mut cursor, seek can have thread local // cursors going let mut sim: usize = 0; let mut cursor = 0; // Calculate the overlap between the query and the found intervals, sum total overlap for i in (0..10).step_by(3) { sim += laps .seek(i, i + 2, &mut cursor) .map(|iv| cmp::min(i + 2, iv.stop) - cmp::max(i, iv.start)) .sum::<usize>(); } assert_eq!(sim, 4);
Structs
Interval | Represent a range from [start, stop) Inclusive start, exclusive of stop |
IterFind | Find Iterator |
IterFindSkip | |
IterLapper | Lapper Iterator |
Lapper | Primary object of the library. The public intervals holds all the intervals and can be used for iterating / pulling values out of the tree. |