Skip to content

Add a Smith-Waterman fallback to support insertion/deletion errors #27

Description

@LTLA

Try to do it the usual way, and if there isn't a suitable hit, we try the fallback if indels are enabled. The "suitability" of the hit depends on the search mode:

  • If we're looking for the best hit, and the best no-indel hit has any number of mismatches, then try a full SW alignment. We need to do it even if there's 1 mismatch because we need to deal with ties and any indel would be tied with a single mismatch. This could be done pretty efficiently as we can constrain the search space by using the no-indel edit distance as an upper bound.
  • If we're looking for the first hit, we use the number of mismatches from the no-indel hit as an upper bound, and then we do a SW alignment based on that. If the upper bound is low enough we might be able to constrain it quite well.
  • If we're looking for any hit, just do the no-indel one first and then try SW if there isn't a suitable hit. Arguably we don't really need the "first" hit, as "any" is good enough.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions