Needleman-Wunsch algorithm

[thin garden]

Hi everyone!! I'm currently working on my very own implementation of the Needleman-Wunsch algortihm. Everything seems to be working just fine and my program passes all kinds of tests, like even very complicated ones. However, one test it is not able to pass. After trying for hours, I hope you guys can help me.

what i got:
PEPTIDE-----
|
------EANANA
-8
expected:
PE-----PTIDE
|
-EANANA-----
-8

due to character limit, my code is attached as pictures

[brazen radish]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[brisk yacht]

!code

[brazen radish]

How to Format Code on Discord

Markup

```cpp
int main() {}
```

Result

int main() {}

Note: Back-tick (`) not quotes (')

[brisk yacht]

hmm

not that one

[thin garden]

should i put the code in the comments?

[brisk yacht]

you can share it on godbolt or pastebin or such

or in multiple messages, sure

[thin garden]

https://godbolt.org/z/crsvG9nac

these are code snippets, lmk if you need more of my code, like my header

[brisk yacht]

NeedlemanWunsch doesn't guarantee any particular optimal solution right

have you checked so if that solution is another correct one?

[thin garden]

you have a very good point!! I believe my solution to be correct as well. However in order to get my points, i need to implement it in such a way with the "right" outcome, which my proffesor thinks to be right and wants as an outcome

[brisk yacht]

😬

there is an interactive needleman wunsch model on the web, have you seen it?

i should be easy to use it to doublecheck if they are both valid solutions

https://bioboot.github.io/bimm143_W20/class-material/nw/

[thin garden]

they all get as optimal path the one my professor wants and i looked up the task again, it specifies what to do when two paths have the same optimal score. first mismatch, then gap in seq2, then gap in seq1. thank you very much for the link. it was great help already!

i tried to switch around the order of vertical and horizontal but it didnt make any difference :(

[brazen radish]

@thin garden Has your question been resolved? If so, type !solved :)

[thin garden]

it still hasnt been solved :(, i dont know what to do, still trying to understand whats wrong exactly

[compact sundial]

does your scorevalue function align with your gap and mismatch penalties, ensuring DIAGONAL is favored over HORIZONTAL and VERTICAL when scores are tied?

[thin garden]

im not sure what you mean by that. my score value function is without any relevance for the order of diagonal, horizontal, vertical. i dont mention them in there. thank you for your help.

[compact sundial]

forgive me, but as I understand it the function will return a score value based on a match, mismatch or gap. Is not not important in determining this score the order in which comparisons are done in determining how penalties or rewards are applied?

[thin garden]

i thought it would just compare two chars? but maybe i dont get the idea.

[compact sundial]

Is there any significance to the penalty applied based the position of a gap?

[thin garden]

no there isnt, each gap is treated withn the same penalty, that is given into the function

[compact sundial]

very well then, please disregard. Sorry for the side-trip.

[thin garden]

no worries, i appreciate any help i can get!! thank you!!

[compact sundial]

Just swap the two input strings and you will get the expected result except with the string order reversed. What this indicates to me is you need to prioritize vertical insertions for s2_ instead of horizontal insertions for s1_.

if (score[i][j] == d) 
    traceback[i][j] = Traceback::DIAGONAL;
else if (score[i][j] == v) 
    traceback[i][j] = Traceback::VERTICAL;
else 
    traceback[i][j] = Traceback::HORIZONTAL;

The traceback order determines how ties are resolved in alignment scoring. By changing the priority, you effectively alter the alignment result without swapping the input strings.

[thin garden]

omg it worked, im really glad i could finally fix this problem!! thank you for your help, i really apreciate it! :D

!solved

[brazen radish]

Thank you and let us know if you have any more questions!

This thread is now set to auto-hide after an hour of inactivity