Quickly Finding K-Mers in Biological Sequences
Explore the efficiency of BLAST in local pairwise alignment to find k-mers of specific score in DNA and protein sequences. Learn about the algorithm's speedy preprocessing methods and how it enhances the search for sequence matches.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
BLAST BNFO 236 Usman Roshan
BLAST Local pairwise alignment heuristic Faster than standard pairwise alignment programs such as SSEARCH, but less sensitive. Online server: http://www.ncbi.nlm.nih.gov/blast
BLAST 1. Given a query q and a target sequence, find substrings of length k (k-mers) of score at least t --- also called hits. k is normally 3 to 5 for amino acids and 12 for nucleotides. Extend each hit to a locally maximal segment. Terminate the extension when the reduction in score exceeds a pre- defined threshold Report maximal segments above score S. 2. 3.
Finding k-mers quickly Preprocess the database of sequences: For each sequence in the database store all k-mers in hash- table. This takes linear time Query sequence: For each k-mer in the query sequence look up the hash table of the target to see if it exists Also takes linear time
