0
$\begingroup$

I have two sequences and I need to perform sequence alignment to determine all possible sequence alignments. I have created the matrix and managed to find 16 alignments.

I wanted to understand if I had correctly approached this because I need to provide all possible alignment sequences and then provide the best alignment sequence/sequences out of all the ones found, however, all my found sequences have a score of -9. The sequences I have found I have placed in this pastebin link: Sequences since I did not want to make the post too large.

I was wondering if someone could help me understand if I may have gone wrong or if I am missing some sequences since all of them have a score of -9. I do not think I have gone wrong during the matrix creation phase but I am unsure. My goal is to find all sequences and not just the optimal ones.

I have asked for help from my tutor however he has been quite rude and reluctant to explain/help so I have decided to turn to the community for help and guidance. Would appreciate any insight into this. Thanks in advance.

Sequence strings:

ggaatggmeeff

gatge

Alignment matrix enter image description here

$\endgroup$

1 Answer 1

2
$\begingroup$

The poster writes “I need to perform sequence alignment to determine all possible sequence alignments”. It is not clear whether this need is that determined by a course assignment or the poster’s mathematical imagination. If the former, I doubt that the wording expresses the request correctly, even though this is repeated in the question as “My goal is to find all sequences and not just the optimal (highest?) ones”. The reason for doubting this is that the number of possible alignments with no restraint imposed will vary from very large to astronomical, depending on the length of the sequences.

The display presented looks at first sight like a trackback for a global alignment using the Needleman and Wunsch dynamic programming algorithm. Such a trackback is designed to find one of what are generally several possible alignments that have the highest score using a specific scoring matrix and gap penalties (different scoring systems can give different alignments). Although it is possible in general to trace alternative trackbacks of the same score manually, I do not see any in this example. This operation is not performed in any programatic implementations of the algorithm of which I am aware. Although, memory limitations permitting, one could program this, the algorithm is not designed to find lower scores (and I find it hard to see the demand for such).

However the problem with the Needleman and Wunsch trackback is that in this algorithm each cell should trackback to the single highest-scoring cell preceding it — if there are two of the same score a random choice is made. But the trackback shown, as well as having instances where the highest scoring cell has been missed, has 9 cases where the trackback is to two cells with different scores. I can think of no justification for this.

There is another fundamental defect here, which arises from the scoring system used. The match = 1, mismatch = –1, fixed-gap-penalty system is doomed to result in low alignment scores in this case: the best possible score is 5 x 1 (matches) + 7 x –2 (gaps) = –9. The PAM or BLOSUM matrix, which score similar amino acids on the basis of their likely mutational substitution and thus are better related to the realities of protein structure, have higher numerical values relative to the gap penalty, which should actually be replaced by a gap initiation penalty followed by a lower gap extension penalty.

In conclusion I would advise anyone undertaking work of this type, first to obtain a thorough understanding of the dynamic programming algorithms used, next to specify clearly the goals he wishes to achieve, then to assess whether they are realistic, and finally be prepared to write a program himself if none already exists.

$\endgroup$
2
  • $\begingroup$ Thanks for the response. We get weekly activities for practice to compliment the lecture. The question states to find all possible alignments, followed by "provide the best alignment sequence/s". However, from my understanding and as you have mentioned, the most optimal alignments are those that go from the most bottom-right to the most top-left. I have managed to find 16, all of which have a score of -9. Since I found them all with the same score, I thought my approach might have been incorrect. My tutor is not polite when you ask for help and so I decided to turn to the community for help. $\endgroup$
    – Krellex
    Apr 13, 2022 at 17:51
  • 1
    $\begingroup$ @Krellex — It's possible for a lecturer to say or write something in a lecture that's ambiguous or not exactly what you intended — I've done it myself many times — and students can sometimes get hold of the wrong end of the stick. It's difficult for someone else to tell. However the generally topic is covered on the web in many places other than the Wikipedia link I gave. Have a look round, and perhaps discuss it with your classmates. Double-check your trackback, and perhaps try a BLOSUM matrix for scoring. $\endgroup$
    – David
    Apr 13, 2022 at 18:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .