Homology searching 1 u
18 important questions on Homology searching 1 u
What does BLAST mean? Name some basic features.
- Heuristic!
- A rule of thumb that often helps in solving a certain class of problems, but makes no guarantees.
- Basic idea:
- Discard putatively unrelated sequences fast
- High scoring segments have well conserved (almost identical) part
- As well conserved segments are identified, extend these to the real alignment
What does well-conserved mean in BLAST?
- BLAST works with k-words (words of length k)
- k is a parameter
- different for DNA (>10) and proteins (2..4), default k values are 11 and 3, resp.
- word w1 is T-similar to w2 if the sum of pair scores is at least T (e.g. T=12)
What are the three basic steps of BLAST?
- Preprocessing: the query sequence: extract all the k-words
- Scan: for T-similar matches in database (fast step)
- Extend: these to final alignments (slow step)
- 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.
Explain the principle of step 2 of BLAST.
- search database for all occurrences of query words
- can be a massive task
- approach:
- build a DFA (deterministic finite-state automaton) that recognizes all query words
- run DB sequences through DFA
- remember hits
What is a DFA, finate state machine?
- abstract machine
- constant amount of memory (states)
- used in computation and languages
- recognizes regular expressions
- cp dmt*.pdf /home/john
BLAST:
- Use all the T-similar k-words to build the Finite State Machine
- Scan for exact matches
What was problematic with classic BLAST? What is different in the current version?
Current BLAST: two-hit method and extention using DP (GappedBLAST).
In the old-BLAST, how dit the extension step work?
(Do'nt immediately stop at -5, because next could be 10). Takes a lot of time --> heuristic method: find diagonal, extend.
- extend hits in both directions without allowing gaps (if score ≥ 13)
- terminate extension in one direction when score falls certain distance below best score for shorter extensions
- return segment pairs scoring at least a threshold score S
Explain the extending step of current BLAST.
- two-hit method
- gapped BLAST
- old extension step typically accounts for 90% of BLASTʼs execution time
- key idea: do extension only when there are two non-overlapping hits on the same diagonal within distance A of each other
- to maintain sensitivity, lower T parameter (T ≥ 11 instead of T ≥ 13)
- more single hits found
- but only small fraction have associated 2nd hit
Contrast classic BLAST and current BLAST.
- Before:
- relatively high T threshold for 3-letter word (hashed) lists • two-way hit extension (see earlier slides)
- Current BLAST: • Lower T: many more hits (more 3-letter words accepted as match)
- Relatively few hits (diagonal elements) will be on same matrix diagonal within a given distance A
- Perform 2-way local Dynamic Programming (gapped BLAST) only on ‘two-hits’ (preceding bullet)
The new way is a bit faster on average and gives better (gapped) alignments and better alignment scores!
What are 2 more recent BLAST developments?
- Indexing (hashing) of the database
- PSI-BLAST
How does an indexed database work?
- Hash the database with k-words
- For each k-word store in which sequences it appears
So when you have a query seq, if there is an exact match, you know immediately the position in the database.
Indexing take lots of time but you do it once (well, you do it again when the database is updated...)
So the speed of the scanning step is improved.
What is the concept of PSI-BLAST?
- Position-Specific Iterated BLAST
- A profile (called PSSM by BLAST – Position Specific Scoring Matrix) is derived from the result of the first search (using a single query sequence)
- Database is searched against the profile (instead of a sequence) in subsequent rounds
- 3 - 10 iterations are recommended
What is a profile?
- a generalized form of sequence (better search capability)
- probabilities instead of a letter
What is a sequence profile matrix?
Profiles may have an extra column (21st position) to describe position-specific gap penalties.
In BLAST a profile is called Position-Specific Scoring Matrix(PSSM) and has only 20 columns (4 for DNA sequences)
How is a profile constructed? (in PSI-BLAST?)
- Take significant BLAST hits
- Make an alignment
- Assign weights to sequences
- Construct profile
In PSI-BLAST, pseudocounts are used in profile construction to make them more reliable.
- useful when multiple alignment contains only few sequences so that there is no statistical sample per column yet
- drawback is pulling all frequencies to prior frequencies, which reduces the differences between sequences
Why are Low-complexity sequences filtered out?
- Low-complexity (sub)sequences have a biased composition and contain less information than high-complexity sequences
- Because of the low information content, they often lead to spurious hits without a biological basis (for example, you can’t tell whether a poly-A sequence [AAAAA...] is more similar to a globin, an immunoglobulin or a kinase sequence)
- That is why BLAST filters low-complexity regions in the query sequence out
What do BLAST and FASTA have in common?
How can the first step of FASTA be made faster.
+ hashing
in fasta with hashing: Algorithmic speed therefore is linear with (DB) sequence length or O(n). Compare this to finding all word match positions without a hash list (complexity is O(m*n)).
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
