search

nanoporetech / pore-c

Pore-C support
Mozilla Public License 2.0
53 stars 6 forks source link

fragment assignment using intervaltree or pybedtools #4

Closed proinde closed 5 years ago

proinde commented 5 years ago

Instead of using bisect search of a fragment position list, using intervaltree to search for fragments overlapped by a mapping. This has the added benefit of (anecdotally) reporting the pct overlap, should that be used in future mapping methods to determine which fragment to report. The downside is that for multi-fragment mappings (i.e. where start and stop don't map to the same fragment), there's about a (1/e)% time cost because searching the start can't be used to pare down the remaining search space.

proinde commented 5 years ago

paring example:

given a (start,stop) identify the fragments. binomial search for start in a fragment list L. this enables binomial search for stop in L[start:], which speeds up the search by 1/e, iirc.