FASTA-A sensitive search engine The early personal computers had insufficient memory and were too slow to carry out a database scan using a rigorous searching method (dynamic programming). Accordingly, Wilbur and Lipman [(1983) Proc. Nat. Acad. Sci. 80, 726-730] developed a fast procedure for DNA scans that in concept searches for the most significant diagonals in a dot plot. FASTA only shows the top scoring region, it does not locate all high scoring alignments between two sequences. As a consequence, FASTA may not directly identify repeats or multiple domains that are shared between two proteins. For more information on the FASTA algorithm, read our FASTA FAQ, or the preprint from the "Protein Sequence Alignment and Database Scanning" chapter in: Protein Structure prediction - a practical approach, edited by M. J. E. Sternberg, IRL Press at Oxford University Press, 1996, ISBN 0 19 963496 3. Please see the book for the final version! Because a FASTA calculation is slow, we can not carry out a 'live' practical. How do I Interpret Fasta Results? Histogram The first part of the output file optionally contains a histogram showing the number of overlapping regions between the query and search set sequences that were observed for each score. !!SEQUENCE_LIST 1.0 (Peptide) FASTA of: unknown.pep from: 1 to: 171 March 3, 1999 10:08 TRANSLATE of: unknown.gcg check: 2624 from: 16 to: 528 generated symbols 1 to: 171. unknown TO: swissprot:* Sequences: 80,780 Symbols: 29,256,406 Word Size: 2 Databases searched: SWISSPROT, Release 37.0, Released on 21Jan1999, Formatted on 26Jan1999 Scoring matrix: GenRunData:blosum50.cmp Variable pamfactor used Gap creation penalty: 12 Gap extension penalty: 2 Histogram Key: Each histogram symbol represents 111 search set sequences Each inset symbol represents 3 search set sequences z-scores computed from opt scores z-score obs exp (=) (*) < 20 169 0 :*= 22 0 0 :* 24 2 0 :* 26 14 2 :* 28 42 18 :* 30 164 111 :*= 32 502 429 :===*= 34 1495 1163 :==========*=== 36 2696 2389 :=====================*=== 38 4221 3949 :===================================*=== 40 5419 5508 :=================================================* 42 6438 6733 :========================================================== * 44 6634 7427 :===========================================================* 46 6301 7565 :========================================================= * 48 5887 7242 :====================================================== * 50 5655 6609 :=================================================== * 52 5215 5810 :=============================================== * 54 4619 4963 :========================================== * 56 4084 4146 :=====================================* 58 3499 3403 :==============================*= 60 2971 2757 :========================*== 62 2653 2210 :===================*==== 64 2499 1758 :===============*======= 66 1814 1389 :============*==== 68 1507 1093 :=========*==== 70 1230 856 :=======*==== 72 992 669 :======*== 74 798 522 :====*=== 76 613 406 :===*== 78 494 316 :==*== 80 421 245 :==*= 82 338 187 :=*== 84 241 149 :=*= 86 199 115 :=* 88 206 89 :*= 90 150 69 :*= 92 115 53 :*= :=================*===================== 94 98 41 :* :=============*=================== 96 67 32 :* :==========*============ 98 78 25 :* :========*================= 100 36 19 :* :======*===== 102 26 15 :* :====*==== 104 17 11 :* :===*== 106 20 9 :* :==*==== 108 16 7 :* :==*=== 110 11 5 :* :=*== 112 10 4 :* :=*== 114 9 3 :* :*== 116 10 2 :* :*=== 118 4 2 :* :*= >120 53 1 :* :*================= Results sorted and z-values calculated from opt score 1909 scores saved that exceeded 80 60154 optimizations performed Joining threshold: 36, optimization threshold: 24, opt. width: 16 The z-score is listed in the leftmost column of the histogram. The second and third columns list the number of observed and expected alignments with that score, respectively. Best Scores Summary Below the histogram, Fasta displays a listing of the best scores. Init1: Smith-Waterman style highest initial score Initn: Smith-Waterman style highest score after allowing diagonals to be joined together (gaps). Opt: Smith-Waterman style optimal alignment score (after rearanging gaps). The z-score of an item, indicates how far and in what direction, that item deviates from its distribution's mean, expressed in units of its distribution's standard deviation. The mathematics of the z score transformation are such that if every item in a distribution is converted to its z score, the transformed scores will necessarily have a mean of zero and a standard deviation of one. Fasta uses a simple linear regression against the natural log of the search set sequence length to calculate a normalised z- score for the sequence pair. In plain english that means that the z-score is independent of the actual Smith-Waterman style score, since that score is dependent on the scoring matrix used. It also negates the length effect, since the length of the sequence influences the Smith-Waterman style score. Expect (E) value: Number of alignments you would expect to see in a database of this size with this z-score. The best scores are: init1 initn opt z-sc E(80533).. sw_release:FLAV_ANASP Begin: 1 End: 169 ! P11241 anabaena sp. (strain pcc 712... 1126 1126 1128 1483.2 0 sw_release:FLAV_SYNP7 Begin: 2 End: 169 ! P10340 synechococcus sp. (strain pc... 699 804 844 1112.6 0 sw_release:FLAV_SYNY3 Begin: 3 End: 165 ! P27319 synechocystis sp. (strain pc... 705 705 823 1085.1 0 sw_release:FLAV_SYNP2 Begin: 2 End: 169 ! P31158 synechococcus sp. (strain pc... 682 773 796 1049.9 0 sw_release:FLAV_TRIER Begin: 1 End: 144 ! O52659 trichodesmium erythraeum. fl... 385 477 697 921.9 0 sw_release:FLAW_ECOLI Begin: 3 End: 167 ! P41050 escherichia coli. flavodoxin... 434 540 570 754.8 2.5e-35 sw_release:FLAV_ECOLI Begin: 4 End: 169 ! P23243 escherichia coli. flavodoxin... 415 505 555 735.2 3.1e-34 . .(Removed bunch of similar lines) . \\End of List If the Fasta search was initiated from within GCG (as the example was), the list of best scores can be used as a GCG list file (See 10 Appendix II: GCG list files). The list file could be the starting file for another analysis, like multiple sequence alignment. Alignments Fasta displays the alignments of the regions of best overlap between the query and search sequences. A ˇ§/revˇ¨ following the query sequence name indicates that the search sequence is aligned with the bottom strand of the query sequence (in DNA searches). This program by default displays only the region of overlap between the two aligned sequences. The display of identities and conservative replacements between the aligned sequences depends on the options selected, the pipe character (|) is used to denote identities and the colon (:) to denote conservative replacements. Note at the end of the summary the CPU time is indicated. This would amount to even more real time since the CPUs are shared between all the different processes running at any one time on the computer. unknown.pep sw_release:FLAV_SYNP7 ID FLAV_SYNP7 STANDARD; PRT; 169 AA. AC P10340; DT 01-MAR-1989 (REL. 10, CREATED) DT 01-JAN-1990 (REL. 13, LAST SEQUENCE UPDATE) DT 15-DEC-1998 (REL. 37, LAST ANNOTATION UPDATE) DE FLAVODOXIN. . . . SCORES Init1: 699 Initn: 804 Opt: 844 z-score: 1112.6 E(): 0 Smith-Waterman score: 844; 70.2% identity in 168 aa overlap 10 20 30 40 50 59 unknown.pep MTKKIGLFYGTQTGKTESVAEIIRDEFGND-VVTLHDVSQAEVTDLNDYQYLIIGCPTWN ||||||||||| |:::|| |::|||:: :| |:|:::|:::||| |:|||||||||| FLAV_SYNP7 AKIGLFYGTQTGVTQTIAESIQQEFGGESIVDLNDIANADASDLNAYDYLIIGCPTWN 10 20 30 40 50 60 70 80 90 100 110 119 unknown.pep IGELQSDWEGLYSELDDVDFNGKLVAYFGTGDQIGYADNFQDAIGILEEKISQRGGKTVG :|||||||||:|::||:|:|:|| |||||:|||:||:||||||:||||||||: |::||| FLAV_SYNP7 VGELQSDWEGIYDDLDSVNFQGKKVAYFGAGDQVGYSDNFQDAMGILEEKISSLGSQTVG 60 70 80 90 100 110 120 130 140 150 160 170 unknown.pep YWSTDGYDFNDSKALRNGKFVGLALDEDNQSDLTDDRIKSWVAQLKSEFGLX || :|||||:|||:||::|||||:||||| ||| :|||:||:|||||||| FLAV_SYNP7 YWPIEGYDFNESKAVRNNQFVGLAIDEDNQPDLTKNRIKTWVSQLKSEFGL 120 130 140 150 160 . .(Removed bunch of simmilar lines) . ! CPU time used: ! Database scan: 0:01:35.3 ! Post-scan processing: 0:00:02.2 ! Total CPU time: 0:01:37.6 ! Output File: /people/tdeboer/aap/unknown_49.fasta