Implement overlap policy

RasmusFonseca commented 9 years ago

Overlap policy should be a modifier setting that determines how a pattern unit tries to find matches. The specific details are a bit vague right now and should be precisely specified, but essentially we want the following policies:

All overlaps (policy 0): Report as many matches as possible, even if they overlap. For "sequence-units" with approximate modifiers (other than mismatches) this means all possible approximate matches should be reported (ATTA/0,1,1 will have 6 matches in the sequence AAATTAAA). For "repeat-units" this means that all valid repetitions will be reported (AA{2,4} will have 6 matches in the sequence CCAAAAAAACC).
Fast (policy 1): Guarantees that if a pattern matches a certain sub-sequence then it will either be reported or another match that overlaps with it will be reported. This policy does not guarantee that overlapping matches are not reported, but it strives to make the implementation as fast as possible. (ATTA/0,1,1 can report as little as 1 match in the sequence AAATTAAA).
Non-overlapping (policy 2): Similar to policy 1, but guarantees that no overlapping matches are reported (ATTA/0,1,1 will have exactly 1 match in the sequence AAATTAAA)

This should of course also be implemented and tested

maasha commented 9 years ago

Is this up to date after we decided to drop the greedy modifier?

RasmusFonseca commented 8 years ago

Policy 0 has been revised:

All overlaps (policy 0): Report as many matches as possible, even if they overlap. For "sequence-units" with approximate modifiers (other than mismatches) this means all possible approximate matches should be reported (ATTA/0,1,1 will have 6 matches in the sequence AAATTAAA). _The "repeat-units" will partially be an exception as they'll behave in a greedy fashion and match as much as they can (AA{2,4} will have 4 matches in the sequence CCAAAAAAACC). This has some counter-intuitive consequences when you have a repeat-unit followed by a pattern unit that matches the same as the repeat-unit, for example, the pattern "A{2,} A" has no matches in the sequence "AAAAC". _

BIO-DIKU / SeqScan

Implement overlap policy #10