Skip to content

Add WatermanSmithBeyer #7

@dawnandrew100

Description

@dawnandrew100

The WatermanSmithBeyer algorithm is an updated version of the NeedlemanWunsch algorithm that uses an affine gap for scoring.

Gotcha for this algorithm:
It is EXTREMELY important when implementing gaps for this function that the pointer matrix not only keep track of whether the best score comes from UP or LEFT but also the optimum number of steps for this specific gap as can be seen below

        for i in range(1, qs_len):
            for j in range(1, ss_len):
                match = self.score[i - 1][j - 1] + self.match_func(qs[i], ss[j])
                ugap = [
                    self.score[i - k][j] + self._gap_func(k) for k in range(1, i + 1)
                ]
                lgap = [
                    self.score[i][j - k] + self._gap_func(k) for k in range(1, j + 1)
                ]
                ugap_score = max(ugap)
                u_step = ugap.index(ugap_score) + 1
                lgap_score = max(lgap)
                l_step = lgap.index(lgap_score) + 1

                tmax = max(match, lgap_score, ugap_score)

                self.score[i][j] = tmax  # highest value is best choice
                pointers = {"pointer": 0, "i_step": 0, "j_step": 0}
                # matrix for traceback based on results from scoring matrix
                if match == tmax:
                    pointers["pointer"] += MATCH
                if ugap_score == tmax:
                    pointers["pointer"] += UP
                    pointers["i_step"] = u_step
                if lgap_score == tmax:
                    pointers["pointer"] += LEFT
                    pointers["j_step"] = l_step
                self.pointer[i][j] = tuple(pointers.values())

In python, this was accomplished by an object type in a numpy array that could hold a dictionary value, but there might need to be either a modification to the Arr2D struct used in goombay-rs or a custom solution that fits Rust

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