Sequence Alignment Algorithms

• Smith-Waterman Algorithm

• FASTA

• BLAST

• Multiple Sequence Alignment

• Hidden Markov Model

• Selected Databases

• Others

Smith-Waterman Algorithm

Smith-Waterman Searches

• Bic-SW uses the Smith-Waterman algorithm to search SwissProt and sends the results back . 
• SSearch on Smith-Waterman search System

• Gotoh, O.  An Improved Algorithm for Matching Biological Sequences.  Journal of Molecular Biology, vol. 162, pp. 705-708, 1982.
• Needleman, S.B., C.D. Wunsch.  A general method applicable to the search for similarities in amio acid asequences of two proteins.  Journal of Molecular Biology, vol. 48, pp. 443-453, 1970. 
• Smith, T.F., M.S. Waterman.  Identification of common molecular subsequences. Journal of Molecular Biology, vol. 147, pp. 195-197, 1981.

• Y. Yamaguchi, T. Maruyama, and A. Konagaya; Pacific Symposium on Biocomputing 7:271-282 (2002). High Speed Homology Search with FPGAs
• C.W. Yu, K.H. Kwong, K.H. Lee and P.H.W. Leong, ``A Smith-Waterman Systolic Cell,'' Proceedings of the Tenth International Workshop on Field Programmable Logic and Applications (FPL'03), Lisbon, pp. 375-384, 2003 .
• Guccione, Steven A., Eric Keller.  Gene Matching Using JBits.  2002.
• Hirshber, Jeffrey D., Richard Hughey, Kevin Karplus.  Kestrel: A Programmable Array for Sequence Analysis.  Proc. Int. Conf. Application-Specific Systems, Architectures, and Processors, IEEE CS, Aug. 19-21, 1996, pp. 25-35.
• Hoang, Dzung T.  FPGA Implementation of Systolic Sequence Alignment.  International Workshop on Field Programmable Logic and Applications, Vienna, Austria, Aug. 31 - Sept. 2, 1992.
• Hoang, Dzung T.  Searching Genetic Databases on Splash 2.  ???. 1993.
• Hughey, Richard.  Massively Parallel Biosequence Analysis.  ???, Apr. 2, 1993.
• Lavenier, Dominique.  SAMBA: Systolic Accelerators for Molecular Biological Applications.  ???, March 1996.
• Lavenier, Dominique.  Speeding up genome computations with a systolic accelerator.  SIAM News, vol. 31, no. 8, Oct. 1998.
• Lipton, Richard J., Daniel Lopresti.  A Systolic Array for Rapid String Comparison.  1985 Chapel Hill conference on VLSI, H. Fuchs, Ed.  Rockville, MD, Computer Science Press, pp. 363-376, 1985.

Papers on Sequence Alignment SIMD Implementation

• Schmidt, B., Schroder, H. and Schimmler, M. Massively Parallel Solutions for Molecular Sequence Analysis, International Parallel and Distributed Processing Symposium: IPDPS Workshops (2002), p. 0186

• Rogens, T. and Seeberg. E. Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors. Bioinformatics, 16, (2000), 699-706.

• Hughey, R. Parallel hardware for sequence comparison and alignment. (1996) Comput. Appl. Biosci. 12, 473-479

• Taylor, Stewart  Applying MMX Technology to the Smith-Waterman Algorithm. Department of Electrical Engineering, Stanford University

• Wozniak, A. (1997) Using video-oriented instructions to speed up sequence comparison. Comput. Appl. Biosci., 13, 145-150.

• TimeLogic - makers of Decypher, an FPGA based Bioinformatics Accelerator
• Compugen - makers of BioXL/H, an FPGA based Bioinformatics Accelerator
• Paracel - makers of GeneMatcher2, a cluster

FASTA

The FastA suite of programs provides methods for searching sequence databases and comparing sequences, as well as some more general analysis programs.

• uses a local alignment method based on matching tuples.
• has empirically determined match statistics, similar to Blast.
• is more sensitive, but slower, if a smaller tuple size is used.

FASTA Searchs

• FASTA Software at University of Virginia

• FASTA3 at EBI

Paper

Pearson, W. R. (2000) Flexible sequence similarity searching with the FASTA3 program package Methods Mol. Biol. 132:185-219

BLAST

Local alignments, Ungapped alignments, Explicit statistical theory, Rapid, Heuristic.

Blast Searches 

• BLAST Software at NCBI

Classic Paper

E. W. Myers, W. Miller, S. F. Altschul, W. Gish and D. Lipman, "Basic Local Alignment Search Tool," Journal Molecular Biology 214, (1990).

Papers on BLAST Parallel Implementation

• Bjornson, R.D., Sherman, A.H., Weston, S.B., Willard, N. and Wing, J. TurboBLAST: A Parallel Implementation of BLAST Built on the TurboHub, International Parallel and Distributed Processing Symposium: IPDPS Workshops (2002), p.0183
• Aaron E. Darling, Lucas Carey, Wu-chun Feng, The Design, Implementation, and Evaluation of mpiBLAST, The HPC Revolution 2003. LA-UR 03-2826
• PARACEL BLAST-Accelerated BLAST software optimized for Linux clusters

• Jlich A., (1995), Implementations of BLAST for parallel Computers, CABIOS 11, 1 (3-6)

• Performance Study of BLAST* on Intel Architecture Technical white paper from Intel Solution Services and Intel Parallel Applications Center

• Yu-Lun Kuo and Chao-Tung Yang Apply Parallel Bioinformatics Applications on Linux PC Clusters Tunghai Science Vol. : 125-141 July, 2003

Multiple Alignment

• CLUSTALW - Multiply Sequence Alignments at IBC-Washington U.  
• AMAS - Analyse Multiply Aligned Sequences.
• Align query - at EERIE
• Multalin - at I.N.R.A.
• Match-Box Web server 1.2. Web page for multiple sequences alignment of proteins.
• Bork's alignment tools - Various tools to enhance the results of multiple alignments (including consensus building).
• CINEMA - Color Interactive Editor for Multiple Alignments
• RandSeq - Random protein sequence generator

Hidden Markov Models

• Lawrence R. Rabiner. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE, VOL 77, NO. 2, Feb 1989
• S.R. Eddy. (1998) Profile hidden Markov models. Bioinformatics , in press. A review of the profile HMM literature from 1996-1998.
• A. Krogh, M. Brown, I.S. Mian, K. Sjolander, D. Haussler. (1994) Hidden Markov models in computational biology: applications to protein modeling. JMB 235:1501-1531. Original profile HMM reference from the Haussler group at UC Santa Cruz.

• S.R. Eddy. (1996) Hidden Markov models. Curr. Opin. Struct. Biol. 6:361-365. Review of profile HMM methods. Provides a number of references for profile HMM applications and available HMM tutorials as of 1996.

• Krogh, A.M. Brown, I.Mian, K. Sjolander and D. Haussler. “Hidden Markov Models in computational Biology: Application to Protein Modeling.” Journal of Molecular Biology 235(1994):1501 - 1531

Selected Databases

    Human

• Human Genome Project Information
• EGAD Expressed Gene Anatomy Database was constructed by extraction and curation of sequences from GenBank to create a non-redundant set of human transcript (HT) sequences at TIGR.
• UNIGENE Human sequences. A gene-oriented view of GenBank sequence entries.
• TIGR Human Gene Index The TIGR Human Gene Index (HGI) integrates research results from international human gene research projects.

    Mouse

• MGI Mouse genome Informatics at the Jackson Laboratory.
• UNIGENE Mouse Sequences A gene-oriented view of GenBank sequence entries.
• TAFGI SRS network Browser for Mouse Databank of Gene Structure and Regulation at Sanger Centre
• TBASE The Transgenic/Targeted Mutation Database

    Yeast

• YPD™ The Yeast Protein Database at Proteome, Inc.
• SGD The Saccharomyces Genome Database at Standford University.
• The yeast proteom database maintained by James I. Garrels
• Yeast 2D map - Bordeaux
• Saccharomyces cerevisiae Genequiz at EBI.

Some other databases

• Databanks of Gene Structure and Regulation at Sanger Centre.
• MIPS genome project page  with several search engines.
• TIGR Database (TDB) is a collection of curated databases containing DNA and protein sequence, gene expression, cellular role, protein family, and taxonomic data for microbes, plants and humans.
• The Merck gene Index.
• Swiss2D SWISS-2DPAGE contains data on proteins identified on various 2-D PAGE reference maps.

Others

Journals

• Nucleic Acids Research
• Bioinformatics
• Journal of Molecular Biology

Book Chapters

• David W. Mount Bioinformatics : sequence and genome analysis. Cold Spring Harbor, N.Y. Cold Spring Harbor Laboratory Press, c2001

• Bryan Bergeron Bioinformatics computing. Upper Saddle River, NJ : Prentice Hall, c2003

Other very useful servers

• National Center for Biotechnology Information (NCBI) - part of the National Library of Medicine and National Institutes of Health Swiss Institute of Bioinformatics
• The CMS Molecular Biology Resource. This website is a compendium of electronic and Internet-accessible tools and resources for Molecular Biology, Biotechnology, Molecular Evolution, Biochemistry, and Biomolecular Modeling. Includes about 1900 links!
• The ExPASy  WWW proteomic tools server of the Swiss Institute of Bioinformatics (SIB).
• CBS Center for Biological Sequence Analysis, The Technical University of Denmark
• HGMP-RC UK . The Human Genome Mapping Project Resource Centre is a body funded by the UK Medical Research Council to provide a Bioinformatics and a Biological service to the UK academic community working on the Human Genome Program and to carry out research in its own right, in a newly formed Research Division.
• Amos' WWW links page One of the most comprehensive websites in bioinformatics.
• All the virology on the www. The website in virology.
• Pedro's BioMolecular Research Tools A Collection of WWW Links to Information and Services Useful to Molecular Biologists.
• Tools at the National  Center for Genome Resources (NCGR).
• EMBL WWW Services.
• Genoscope , the Frensh sequencing centre.
• Bruker Mass Spectrometry Instrument