Pairwise alignment II
13 important questions on Pairwise alignment II
What is a problem with the simple dynamic programming approach?
- It can only do linear gap penalties
- The algorithm can be extended to deal with affine gap penalties
How can the simple dynamic programming approach be extended to deal with affine gap penalties?
g(k) = b + ak
b = penalty for opening a gap
a = penalty for extending a gap
We look back to not only the standard three cells (above, diagonal, left), but to four more.
With affine, it matters if the gap is the starter of one or more gaps next to each other, or if it follows after an already existing gap.
(schermopname 20)
What is the time and memory complexion of DP?
- Time complexity: O (n^2) for aligning two sequences of n residues, you need to perform n^2 algorithmic steps: matrix size
- different seq lenghts: (m * n)
- Memory space complexity: also O(n^2): you need a square search matrix of n by n containing n^2 cells
- Higher grades + faster learning
- Never study anything twice
- 100% sure, 100% understanding
For my 1st exam I got a C. Then, I started looking for ways to learn better and I came across Study Smart. Since then I have scored a A+, A, A- and another A. I highly recommend it to everyone who wants to hear it. I am so happy with it!!
I was struggling to finish all my first-year subjects for 3 years. Then I discovered Study Smart, which helped me to finish all of them within 3 months.
Because of StudySmart, things are going well in many ways. Before, I always had study stress and no time for anything. Now I feel calm and confident (because of the program). I used to score a B, now I usually score an A or A+.
Hey Chris, I really want to thank you very much for developing the platform, I usually got around C for my exams, now I scored an A+, an A and a A- !!
Since using Study Smart, my average has increased significantly. I even completed a statistics course with a A+ while I'm bad at statistics. I took on extra courses this year, because of Study Smart. Thanks so much!
Ever since I started studying with StudySmart I passed all my exams !!! No more re-sits!! At first, I was happy with a pass and now I only get good grades. Many thanks!
I aced all the courses I studied with Study Smart. For law, I first scored a D, and now an A! I’m 100% sure that I’ll pass all the courses I study with Study Smart.
I always thought I studied well. My grades were fine. I could never have imagined that applying these study skills would have such a huge and direct impact on my grades, my speed and the pleasure I have in learning.
For the first time, I finally feel totally confident about the way I learn. I have the perfect overview and make great progress in terms of speed and the grades I get. Thanks, Chris!
I immediately started to enjoy learning again, and my grades soared. All of a sudden, everything went better. I highly recommend Study Smart to all students..
Being able to create my materials online made the process of studying so much smoother and quicker. I no longer have to spend a huge amount of my time on creating my summaries.
At first, my notes were a mess. Now I use Study Smart to take my notes in a perfectly structured way. It helps me to save a lot of time and do other things I enjoy.
Students that study with Study Smart get better grades. The system applies all the learning methods in such a way that both well-performing students and students who struggle perform much better.
Hi Chris, I would like to thank you very much. Last year I scored C on a course, and this year I got an A+ thanks to your method! Thank you very much!
The largest effect is that my child is more enthusiastic about school! Every parent wants their children to be happy at school, Study Smart made it happen.
In high school, I failed several exams, and that has really changed now. I actually needed this tool very much back then. Since I started studying with StudySmart, I haven't had any D's. My average score is now an A and those are results I would have never had in the past
With my old method, I passed only 3 out of 8 courses. Since I started taking my notes digitally in Study Smart, I have passed all my courses on the first try. For me, StudySmart takes away the stress of wondering if I will pass or not.
Thanks to StudySmart, I passed all my exams, and with better grades than before! On top of that, I have mastered a very good study method now, which I am confident will help me earn my degree.
How does an alternative DP approach work, suitable for all types of gap penalties? This alternative approach is called general DP algorithm.
Complexity is increased from O(n^2) to O(n^3).
The gap length is known exactly, therefore any gap penalty regime can be applied.
*check this again. Slide 30, 31
Name three situations when you would want to use semiglobal alignment. Also name a risk.
- Finding a gene in a genome
- Placing marker onto a chromosome
- When one sequence is much longer than the other one
Risk: if the gap penalty is high, really bad alignment for divergent sequences.
Where do you find the alignment score and start of the traceback for global, semiglobal and local alignment?
- Global: bottom right cell
- Semiglobal: max value of bottom row or most right column
- Local: max value of the whole matrix
Why/in which cases would you use local alignment? (2)
- Parts of sequence diverge faster
- evolutionary pressure is not present on whole sequence
- consider high vs low conserved regions
- Proteins have modular construction:
- sharing domains between sequences
- so eg aligned region occurs twice in sequence x, once in seq y
How is the equation changed for local alignment?
Adding the 0 also works for alternative DP for all gap penalties: also add 0 as option for the equation (see slide 57).
How can you find the second best alignment?
- Best alignment surrounded by clump: clump of alignment = alignments sharing at least one aligned pair.
- Don't let any matched pair contribute to the next alignment:
- clear the best alignment (set all values of this path to 0)
- recalculate the clump
- Now find the next best alignment and repeat this
- This is called Waterman-Eggert algorithm
Useful for eg protein with repeats, those domains may differ slightly but you want to align them all.
What are two pitfalls of alignments?
- Alignment is often not a reconstruction of evolution: common ancestor is usally extinct
- Repeats: matches to the same fragment!
What does protein research tell us about requirements for alignment techniques? (4)
- Alignments need to be able to skip secondary structural elements to complete domains (ie putting gaps opposite these features in shorter sequences).
- Gap situations can be even more complex in cases of alternatively spliced protein variants.
- Depending on chosen gap penalty, algorithm might have difficulty with making such lang gaps --> incorrent alignment.
- Alignments are only meaningful for homologous sequences.
What are dot plots?
- Way of representing sequence similarity without DP
- Make search matrix as for DP, but locally represent sequence similarity by averaging using a sliding window.
- A dot is placed in every place where row and column contain same character.
Name 4 features to quantify sequence similarity.
- Sequence identity: number of identical exchanges per unit length
- Raw alignment score
- Sequence similarity (alignment score normalized to a maximum possible)
- Alignment score normalised to a randomly expected situation
- Z-score
The question on the page originate from the summary of the following study material:
- A unique study and practice tool
- Never study anything twice again
- Get the grades you hope for
- 100% sure, 100% understanding
