Skip to content
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.

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

Refactor selection of Myers' bitparallel edit distance algorithm. #3254

Merged

Conversation

rrahn
Copy link
Contributor

@rrahn rrahn commented May 15, 2024

This PR fixes #3253 by:

  1. adding a new dedicated scoring scheme for enabling hamming distance, which is agnostic to the alphabet type,
  2. switching to use this hamming scoring scheme in the edit scheme alignment configuration and test for it during the alignment configuration.

Due to these changes, users can select the Myers' bitparallel edit distance alignment computation independent of their alphabet types and thus are not forced to work with the nucelotide scoring scheme anymore, which did not allow to customize the alphabet type.
Since the bitparallel edit distance algorithm doesn't even read the values from the given scoring schemes, it makes only sense to enable it without specifying a dedicate scoring scheme anyway.
However, due to the existing configuration modes, too much API breakage would have been introduced if wanted to solve this by moving the bitparallel edit distance computation into its own configuration element.
With this solution the user won't see any difference to the old version, when sticking to the tuorials where we explicitly teach to use the dedicated align_cfg::edit_scheme shortcut.

rrahn added 4 commits May 15, 2024 16:01
This scheme is alphabet agnostic and used to trigger the myers' bitparallel algorithm to compute the edit distance.
It is a special case of the DP alignment algorithm where the score for a substitution is 0 if the characters are equal and -1 otherwise.
…eme which is implementation detail and actually not required by the scoring scheme concept.
…ure Myers' bitparallel edit distance computation.

Now the edit distance is selected internally if the hamming scheme was used explicitly and if the gap scheme gives -1 for extending and 0 for opening a gap.
The edit distance can now be used independent of the alphabet type and is not bound to seqans nucleotide scoring schemes.
Since the recommended way to enable the fast bitparallel algorithm is to use the `align_cfg::edit_scheme` configuration element, the majority of user code should work without noticing the internal changes made to the configuration.
…rithm.

It makes more sense to skip the runtime checks if the compiler already knows that no Myers' bitparallel edit distance cannot be used.
Copy link

vercel bot commented May 15, 2024

The latest updates on your projects. Learn more about Vercel for Git ↗︎

Name Status Preview Updated (UTC)
seqan3 ✅ Ready (Inspect) Visit Preview May 29, 2024 9:13am

@seqan-actions seqan-actions added the lint [INTERNAL] signal for linting label May 15, 2024
@rrahn rrahn requested a review from eseiler May 15, 2024 14:28
@seqan-actions seqan-actions removed the lint [INTERNAL] signal for linting label May 15, 2024
rrahn added 4 commits May 16, 2024 11:08
… algorithm.

During configruation we check if the gap scheme is set and if not use the default gap scheme with `gap open = 0` and `gap extension = -1`. But this default gap scheme is ignored and was later set to -10 and -1 in the alignment gap policy.
This commit fixes this, to keep the defaults consistent.
@seqan-actions seqan-actions added the lint [INTERNAL] signal for linting label May 16, 2024
@seqan-actions seqan-actions removed the lint [INTERNAL] signal for linting label May 16, 2024
Copy link
Member

@eseiler eseiler left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good, only small stuff

@seqan-actions seqan-actions added lint [INTERNAL] signal for linting and removed lint [INTERNAL] signal for linting labels May 28, 2024
@seqan-actions seqan-actions added lint [INTERNAL] signal for linting and removed lint [INTERNAL] signal for linting labels May 28, 2024
@rrahn rrahn force-pushed the refactor/dedicated_edit_distance_scoring_scheme branch from 0b90d3a to 267bd9b Compare May 28, 2024 17:01
@seqan-actions seqan-actions added lint [INTERNAL] signal for linting and removed lint [INTERNAL] signal for linting labels May 28, 2024
@seqan-actions seqan-actions added lint [INTERNAL] signal for linting and removed lint [INTERNAL] signal for linting labels May 29, 2024
@seqan-actions seqan-actions added lint [INTERNAL] signal for linting and removed lint [INTERNAL] signal for linting labels May 29, 2024
@rrahn rrahn force-pushed the refactor/dedicated_edit_distance_scoring_scheme branch from 69350fd to 267bd9b Compare May 29, 2024 10:02
@seqan-actions seqan-actions added lint [INTERNAL] signal for linting and removed lint [INTERNAL] signal for linting labels May 29, 2024
@rrahn rrahn requested a review from eseiler May 29, 2024 10:03
@eseiler eseiler merged commit 41a17ad into seqan:main May 31, 2024
59 of 63 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Allow min_score alignment config for arbitrary (user defined) edit distance schemes
3 participants