Introduction to Information Retrieval

This is the companion website for thefollowing book.

Christopher D. Manning,Prabhakar Raghavanand HinrichSchütze,Introduction to Information Retrieval, CambridgeUniversity Press. 2008.

You can order this bookat CUP, at your local bookstore or on the internet. The best searchterm to use is the ISBN:0521865719.

The book aims to provide a modern approach to information retrieval from a computer science perspective.It is based on a course we have been teaching invarious forms at Stanford University and at theUniversity of Stuttgart.

We'd be pleased to get feedback about how this book works out as a textbook,what is missing, or covered in too much detail, or what is simplywrong. Please send any feedback or comments to:informationretrieval (at) yahoogroups (dot) com

Online resources

Apart from small differences (mainly concerning copy editing and figures), the online editions should have the same content as the print edition. However, we are planning to fix errata in the online editions every few months or so.

The following materials are available online. The date of last update is given in parentheses.

• HTMLedition (2008.06.01)
• PDFof the book for online viewing (with nice hyperlink features, 2008.07.12)
• PDFof the book for printing (2008.05.27)
• PDFs of individual chapters (2008.05.27)
• slides (2008.07.12)
• discussion forums (2008.08.13)
• a moodle with interactive exercises (2008.08.13)
• solutionsto the exercises (2007.12.31, you will need to register with CUP)
• errata (2008.07.12)

Information retrieval resources

Alist of informationretrieval resources is also available.

Introduction to Information Retrieval: Table of Contents

Algorithm

To run, BLAST requires a query sequence to search for, and asequence to search against (or a sequence database containing multiplesuch sequences)(also called the target sequence). BLAST will findsubsequences in the database which are similar to subsequences in thequery. In typical usage, the query sequence is much smaller than thedatabase, e.g., the query may be one thousand nucleotides while thedatabase is several billion nucleotides.

The main idea of BLAST is that there are often high-scoring segmentpairs (HSP) contained in a statistically significant alignment. BLASTsearches for high scoring sequence alignments between the query sequence and sequences in the database using a heuristic approach that approximates the Smith-Waterman algorithm. The exhaustive Smith-Waterman approach is too slow for searching large genomic databases such as GenBank. Therefore, the BLAST algorithm uses a heuristicapproach that is less accurate than the Smith-Waterman but over 50times faster. The speed and relatively good accuracy of BLAST are amongthe key technical innovation of the BLAST programs.

Here the algorithm of BLASTP (a protein to protein search) is introduced to present the concept of BLAST.^[4]

1. Remove low-complexity region or sequence repeats in the query sequence.
   Low-complexity region means a region of a sequence is composed of fewkinds of elements. These regions might give high scores that confusethe program to find the actual significant sequences in the database,so they should be filtered out. The regions will be marked with an X(protein sequences) or N (nucleic acid sequences) and then be ignoredby the BLAST program. To filter out the low-complexity regions, the SEG program is used for protein sequences and the program DUST is used for DNA sequences. On the other hand, the program XNU is used to mask off the tandem repeats in protein sequences.
2. Make a k-letter word list of the query sequence.
   Take k=3 for example, we list the words of length 3 in the queryprotein sequence (k is usually 11 for a DNA sequence) “sequentially”,until the last letter of the query sequence is included. The method canbe illustrated in figure 1.
   

   Fig. 1 The method to establish the k-letter query word list.
3. List the possible matching words.
   This step is one of themain differences between BLAST and FASTA. FASTA cares about all of thecommon words in the database and query sequences that are listed instep 2; however, BLAST cares about only the high-scoring words. Thescores are created by comparing the word in the list in step 2 with allthe 3-letter words. By using the scoring matrix (substitution matrix)to score the comparison of each residue pair, there are 20^3 possiblematch scores for a 3-letter word. For example, the score obtained bycomparing PQG with PEG and PQA is 15 and 12, respectively. For DNAwords, a match is scored as +5 and a mismatch as -4. After that, aneighborhood word score threshold T is used to reduce the number ofpossible matching words. The words whose scores are greater than thethreshold T will remain in the possible matching words list, whilethose with lower scores will be discarded. For example, PEG is kept,but PQA is abandoned when T is 13.
4. Organize the remaining high-scoring words into an efficient search tree.
   This is for the purpose that the program can rapidly compare the high-scoring words to the database sequences.
5. Repeat step 1 to 4 for each 3-letter word in the query sequence.
6. Scan the database sequences for exact match with the remaining high-scoring words.
   The BLAST program scans the database sequences for the remaininghigh-scoring word, such as PEG, of each position. If an exact match isfound, this match is used to seed a possible ungapped alignment betweenthe query and database sequences.
7. Extend the exact matches to high-scoring segment pair (HSP).
   • The original version of BLAST stretches a longer alignment betweenthe query and the database sequence in left and right direction, fromthe position where exact match is scanned. The extension doesn’t stopuntil the accumulated total score of the HSP begins to decrease. Asimplified example is presented in figure 2.
     

     Fig. 2 The process to extension the exact match.
   • To save more time, a newer version of BLAST, called BLAST2 orgapped BLAST, has been developed. BLAST2 adopts a lower neighborhoodword score threshold to maintain the same level of sensitivity fordetecting sequence similarity. Therefore, the possible matching wordslist in step 3 becomes longer. Next, the exact matched regions, withindistance A from each other on the same diagonal in figure 3, will bejoined as a longer new region. Finally, the new regions are thenextended as the same method in the original version of BLAST, and theHSPs’ (High-scoring segment pair) scores of the extended regions arethen created by using a substitution matrix as before.
     

     Fig. 3 The positions of the exact matches.
8. List all of the HSPs in the database whose score is high enough to be considered.
   Welist the HSPs whose scores are greater than the empirically determinedcutoff score S. By examining the distribution of the alignment scoresmodeled by comparing random sequences, a cutoff score S can bedetermined such that its value is large enough to guarantee thesignificance of the remained HSPs.
9. Evaluate the significance of the HSP score.
   BLAST next assesses the statistical significance of each HSP score by exploiting the Gumbel extreme value distribution (EVD).(It is proved that the distribution of Smith-Waterman local alignmentscores between two random sequences follows the Gumbel EVD, regardlessof whether gaps are allowed in the alignment). In accordance with theGumbel EVD, the probability p of observing a score S equal to orgreater than x is given by the equation
   
   ,where
   
   The statistical parameters λ and Kare estimated by fitting the distribution of the ungapped localalignment scores, of the query sequence and a lot of shuffled versions(Global or local shuffling) of a database sequence, to the Gumbelextreme value distribution. Note that λ and Kdepend upon the substitution matrix, gap penalties, and sequencecomposition (the letter frequencies).The m’ and n’ is the effectivelength of the query and database sequence, respectively. The originalsequence length is shortened to the effective length to compensate forthe edge effect (an alignment start near the end of one of the query ordatabase sequence is likely not to have enough sequence to build anoptimal alignment). They can be calculated as
   
   ,
   where His the average expected score per aligned pair of residues in analignment of two random sequences. Altschul and Gish gave the typicalvalues, λ = 0.318, K = 0.13, and H = 0.40, for ungapped local alignment using BLOSUM62as the substitution matrix. Using the typical values for assessing thesignificance is called the lookup table methods, it is not accurate.Theexpect score E of a database match is the number of times that anunrelated database sequence would obtain a score S higher than x bychance. The expectation E obtained in a search for a database of Dsequences is given by
   
   Furthermore, when p < 0.1, E could be approximated by the Poisson distribution as
   
   Note that the E value accessing the significance of the HSP score here(for ungapped local alignment) is not identical to the one in the laterstep to evaluate the final gapped local alignment score, due to thevariation of the statistical parameters.
10. Make two or more HSP regions into a longer alignment.
    Sometimes, we find two or more HSP regions in one database sequencethat can be made into a longer alignment. This provides additionalevidence of the relation between the query and database sequence. Thereare two methods, the Poisson method and the sum-of scores method, tocompare the significance of the newly combined HSP regions. Supposethat here are two combined HSP regions with the sets of score (65, 40)and (52, 45), respectively. The Poisson method gives more significanceto the set with the lower score of each set is higher (45>40).However, the sum-of-scores method prefers the first set, because 65+40(105) is greater than 52+45(97). The original BLAST uses the Poissonmethod; gapped BLAST and the WU-BLAST use the sum-of scores method.
11. Show the gapped Smith-Waterman local alignments of the query and each of the matched database sequences.
    • The original BLAST only generates ungapped alignments including theinitially found HSPs individually, even when there is more than one HSPfound in one database sequence.
    • BLAST2 versions produce a single alignment with gaps that caninclude all of the initially found HSP regions. Note that thecomputation of the score and its corresponding E score is involved withthe adequate gap penalties.
12. Report the matches whose expect score is lower than a threshold parameter E.