8000 Reimplement the current alignment::Aligner without breaking API by TianyiShi2001 · Pull Request #379 · rust-bio/rust-bio · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Reimplement the current alignment::Aligner without breaking API #379

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
wants to merge 28 commits into
base: master
Choose a base branch
from
Open

Reimplement the current alignment::Aligner without breaking API #379

wants to merge 28 commits into from

Conversation

TianyiShi2001
Copy link
Member

Faster global, local, semiglobal alignment with less space usage. Related to #354 and #355 (review).

All tests are unchanged and passed. No breaking changes. The API is completely unchanged.

Old(a1b1143):

test bench_aligner_wc_global     ... bench: 549,914,573 ns/iter (+/- 66,950,334)
test bench_aligner_wc_local      ... bench: 648,835,834 ns/iter (+/- 93,166,340)
test bench_aligner_wc_semiglobal ... bench: 622,027,993 ns/iter (+/- 43,517,887)

New:

test bench_aligner_wc_global     ... bench: 117,967,967 ns/iter (+/- 11,637,569)
test bench_aligner_wc_local      ... bench: 220,659,055 ns/iter (+/- 18,904,199)
test bench_aligner_wc_semiglobal ... bench: 152,071,703 ns/iter (+/- 11,597,219)

I didn't implement the "custom" alignment bacause it seemed not very useful. I haven't seen this type of alignment other than in SeqAn and rust-bio. Maybe this will be discussed in another issue.

TianyiShi2001 and others added 20 commits September 6, 2020 09:17
@TianyiShi2001
improve docs of bio::alignment::pairwise
752ab77 
- fix two typos
- add internal links
- fix format (schematics in code blocks; proper new lines)
@TianyiShi2001
improve docs for bio::alignment::pairwise
7c4eb6f
@TianyiShi2001
ignore non-node
28b6428
@TianyiShi2001
idomatic assignment
ca790a2
@TianyiShi2001
idiomatic
4f2e943
@TianyiShi2001
remove repetition
9c174b5 
repitition of line 559: self.S[k].extend(repeat(MIN_SCORE).take(m + 1));
@TianyiShi2001
Improve algorithm of alignment::pairwise
efb6390
@TianyiShi2001
fix the bug
4f51e40 
now passes all tests!
@TianyiShi2001
benchmark
a96e3b6 
a commit for comparing the benchmarks of the old aligner and the new one.
To be restored later
@TianyiShi2001
restore
d43bac0
@TianyiShi2001
Merge branch 'ts-improve-docs' into aligner-restructure
b956e36
@TianyiShi2001
update docs
e7dad84
@TianyiShi2001
add reference
b5f9424
@dlaehnemann
Merge branch 'master' into aligner-restructure
464b45a
@TianyiShi2001
Create fast.rs
64eb1a5
@TianyiShi2001
Merge branch 'seq-aln' into fast-alignment
8e77748
@TianyiShi2001
Create fast.rs
bf9e89d
@TianyiShi2001
reimplement the fast but O(nm) space alignment algorithm
5e2c730 
All tests are unchanged and passed.
@TianyiShi2001
Merge branch 'aligner-restructure' into fast-alignment
e569e4f
@TianyiShi2001
removing mut
1b9aece
@TianyiShi2001 TianyiShi2001 mentioned this pull request Oct 3, 2020
Closed
TianyiShi2001 added a commit that referenced this pull request Oct 3, 2020
@TianyiShi2001
remove pairwise::fast; open a separate PR
879e8ac 
#379
@TianyiShi2001 TianyiShi2001 mentioned this pull request Oct 3, 2020
Draft
@TianyiShi2001
Copy link
Member Author
TianyiShi2001 commented Oct 3, 2020 •
edited
Loading

TODO

  • update docs
  • deprecation warning of with_capacity methods
  • bypass clippy warning with justification

@TianyiShi2001
Copy link
Member Author

This will partially fix #377

@TianyiShi2001
Copy link
Member Author

I want to deprecate with_capacity because the time taken to initialize a few vectors is almost negligible when compared to the alignment computation as a whole.

In addition, if the aligner first aligns large sequences and allocates a big capacity, and then aligns short sequences, there will be a significant waste of memory

ChallengeDev210 pushed a commit to ChallengeDev210/rust-bio that referenced this pull request Aug 1, 2022
@TianyiShi2001
remove pairwise::fast; open a separate PR
d2e4cb4 
rust-bio/rust-bio#379
@maxall41
Copy link

This is really great work! Has any progress been made on this?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
WIP
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@TianyiShi2001 @maxall41 @dlaehnemann
0