Improvements to (bi_)fm_index::cursor

seqan / product_backlog

This repository is used as product backlog for all SeqAn relevant backlog items. This is intended to organise the work for the team.

2 stars 1 forks source link

Improvements to (bi_)fm_index::cursor #284

Open marehr opened 3 years ago

marehr commented 3 years ago

Description

This is currently just a placeholder, @SGSSGene will fill this with details.

As I want so I can

Acceptance Criteria

[ ] test 1
[ ] test 2
[ ] test 3

Tasks

- [ ] task 1 - [ ] task 2 - [ ] task 3 ### Definition of Done - [ ] Implementation and design approved - [ ] Unit tests pass - [ ] Test coverage = 100% - [ ] Microbenchmarks added and/or affected microbenchmarks < 5% performance drop - [ ] API documentation added - [ ] Tutorial/teaching material added - [ ] Test suite compiles in less than 30 seconds (on travis) - [ ] Changelog entry added

marehr commented 3 years ago

Core 2021-01-27

Simon presented some ideas to simplify the cursor.

cursor:

same redundant variables should be removed

bi_fm_index:

swap sampling rates, to improve the locate function

(no guarantee for completeness)

SGSSGene commented 3 years ago

FM-Index

Change (Bi-Cursor)
- too many member variables
- only need (IndexPtr, fwd_lb, rev_lb, range)
- change BI-Index: sparse index should be the rev_index (otherwise cursor needs to track depth)
- BI-Cursor does self modification (extend_left, extend_right)
- remove cycle and only do extend_left and extend_right (no self-modification)
- This will require changes in the search algorithms
FM-Index: should this really reverse the index by default?
conversion from alphabet to rank, where is the best place? index, cursor?