Introduction to computer science

• www.compume.com
• www.grassrootsdesign.com
• www.fayette.k12.il.us
• www.glencoe.com
• www.comedition.com
• www.hitmill.com
• www.pstcc.cc.tn.us

Introduction to Internet

• oac3.hsc.uth.tmc.edu
• www.cisco.com
• http://www.ch.embnet.org

Basics of HTML

• www.htmlgoodies.com
• www.bfree.on.ca
• www.pagetutor.com
• www.davesite.com
• www.webreference.com
• www.pageresource.com
• http://www.devry-phx.edu
• http://www.ncsa.uiuc.edu
• http://www.w3.org/
• http://archive.ncsa.uiuc.edu

Java Tutorial

• java.sun.com/docs/books/tutorial/
• developer.java.sun.com/developer/onlineTraining/
• javaboutique.internet.com/tutorials/
• www.freewarejava.com/tutorials/index.shtml
• www.javacoffeebreak.com/tutorials/
• www.apl.jhu.edu/~hall/java/FAQs-and-Tutorials.html
• http://www.javaworld.com/
• http://www.simplilearn.com/resources-to-learn-java-programming-article

Perl Tutorials

• www.devdaily.com/perl/
• www.pageresource.com/cgirec/index2.htm
• www.perl.com/pub/q/resources
• www.perlmonks.org
• Perl for Biologists (Weizmann Institute)
• www.webknowhow.net/dir/Perl/Tutorials/
• Perl for Biologists
• savage.net.au/Perl-tutorials.html
• Welcome to the Bioperl Project !

XML Tutorial

• www.w3schools.com
• www.zvon.org
• www.xmlfiles.com
• wdvl.internet.com
• www.finetuning.com

SQL Tutorial

• www.sqlcourse.com/
• www.w3schools.com/sql/default.asp
• www.sqlcourse2.com/
• php.weblogs.com/sql_tutorial
• perl.about.com/cs/beginningsql/
• www.db.cs.ucdavis.edu/teaching/sqltutorial/

Oracle Tutorial

• www.hot-oracle.com/
• www.oraclepower.com/
• www.oraclepower.com
• www.orafaq.org/suptutor.htm
• www.vb-bookmark.com/OracleTutorial.html

C and C++ Tutorial

• www.cyberdiem.com/vin/learn.html
• www.webwareindex.com/tutorials/C.html
• www.cprogramming.com/tutorial.html
• www.gustavo.net/programming/c__tutorials.shtml
• dmoz.org/Computers/Programming/Languages/C/Tutorials/

CGI Tutorial

• www.htmlgoodies.com/beyond/cgi.html
• www.cgi-resources.com/Documentation/CGI_Tutorials/
• www.gustavo.net/programming/cgi.shtml
• www.cgidir.com/Tutorials/
• webdesign.about.com/cs/cgi/
• http://www.cgi101.com/class/

Unix Tutorial

• www.ee.surrey.ac.uk/Teaching/Unix/
• webreference.com/programming/unix/
• www.uwsg.iu.edu/uhelp/tutorials/toc.html
• www.unixtools.com/tutorials.html
• www.networkcomputing.com/unixworld/ archives/tutorials.html
• www.unix-manuals.com/
• http://www.isu.edu/departments/comcom/unix/workshop/unixindex.html
• http://www.ee.surrey.ac.uk/Teaching/Unix/
• http://www.linuxnewbie.org/

Basics of Biology

• scidiv.bcc.ctc.edu
• library.thinkquest.org/12413/
• www.biology-online.org/tutorials/home.htm
• www.lsic.ucla.edu/ls3/tutorials/
• biology-online.org/
• Cartoon Guide to Genetics
• genomebiology.com/tutorials/
• http://biomed.nus.sg/HIS/txt/menu/tacmenu.html
• Tutorials in Molecular Biology
• http://www.iacr.bbsrc.ac.uk
• BioBook Glossary
• Highveld.com - Internet Directory of Biology and Biotechnology
• ESG Biology Hypertextbook Home Page
• DOE Primer on Molecular Genetics

Basics of Chemistry

• www.chemistrycoach.com/tutorial.htm
• users.rcn.com/bobsalsa/tutorial.htm
• lrc-srvr.chemistry.ohio-state.edu
• http://www.unm.edu/~dmclaugh
• http://www.chem.umr.edu
• http://www.chem.umr.edu
• http://turner.lamf.uwindsor.ca
• http://www.chem.vt.edu
• Periodic table of the elements
• Interactive periodic table of the elements
• http://chem.answers.com/periodic-table

Introduction to BioChemistry

• www.biology.arizona.edu/biochemistry/biochemistry.html
• www.umanitoba.ca/faculties/medicine/biochem/tutorials/
• www.ahpcc.unm.edu/~aroberts/main/ biochemistry_tutorials.htm
• www.massey.ac.nz/~wwbioch/Prot/tutehome/tutepage.htm
• xray.bmc.uu.se/Courses/Bke1/Tutorials/ Tutorialindex.html
• http://www.jonmaber.demon.co.uk/

Understand DNA

• biog-101-104.bio.cornell.edu/BioG101_104/ tutorials/recomb_DNA.html
• avery.rutgers.edu/WSSP/Tutorials/ (chime plugin required)
• www.umass.edu/molvis/freichsman/
• www.tutorgig.com/showurls.jsp?group=6732&index=0
• www.scientific.org/tutorials/articles/riley/riley.html
• www.tulane.edu/~biochem/nolan/lectures/rna/intro.htm
• http://lenti.med.umn.edu/recombinant_dna/recombinant_flowchart.html
• DNA tutorial
• DNA from the beginning
• Central Dogma Glossary

About RNA

• www.imsb.au.dk/~raybrown/
• zombie.imsb.au.dk/~raybrown/
• ndbserver.rutgers.edu/NDB/structure-finder/ tutorials/full_ndb.dna.rna.res.html

About Genome

• genomebiology.com/tutorials/
• http://www.genomeweb.com/
• anatomy.med.unsw.edu.au/cbl/GENOME/tutorials.htm
• rsat.ulb.ac.be/rsat/tutorials/ tut_genome-scale-patser.html
• home.uchicago.edu/~ebetran/guides.html
• Basic Genome Glossary
• Limited Genome Glossary
• Genome Glossary
• The Gene-School Glossary
• Glossary of Genetic Terms

 Similarity Search Tutorials

• An Overview of Sequence Comparison Algorithms in Molecular
• Bill Pearson talks about Protein Evolution
• Biological Sequences and Information
• BLAST HELP MANUAL
• BLAST tutorial
• Pedestrian guide to analysing sequence databases
• Sequence Comparison (Keith Robison)
• Database Research at Penn

• Biology, E. W. Myers
• Bill Pearson talks about Fasta
• Bioinformatics: Elementary Sequence Analysis, Brian Golding and Dick Morton
• Distant homologies: motifs, patterns, profiles
• A Guide to Molecular Sequence Analysis
• Exploring Distant Protein Sequence Relationships
• Sequence Analysis tutorial
• The Sequence and Structure Searching Site
• Flexible Information Visualization of Multivariate Data from Biological
• Sequence Similarity Searches

Feel free to add more useful tutorial links for bioinformaticians in comment section. 

1. Accelrys Software Solution Pvt Ltd.
12th Floor, Discover, ITPL, White Field, Bangalore-65.
www.accelrys.com

2. Apticraft Systems (P) Ltd.
142, Electronics Complex, Pardeshipura, Indore – 452010 (M.P.), India
www.apticraft.com

3. Aptuit Informatics
Plot No. 100-103, Export Promotion Industrial Park, White Field, Bangalore-560066
www.aptiuit.com

4. Bigtec
J. K. Towers, 8th Block, Sangam Circle,46th Cross, Bangalore-560082.
www.bigtec.org

5. Bijam Biosciences Private Limited
Nagarjuna Hills, Hyderabad 500 082, India
www.nagarjunagroup.com

6. Bio Base Databases India Pvt Ltd.
Crescent Towers, 4th Floor, No : 32/1, Crescent Road, Bnagalore – 560 001
www.biobase-international.com

7. BioImagene India Pvt. Ltd.
4th floor, C-Wing, Godrej Eternia, Shivajinagar, Pune-411005
www.bioimagene.com

8. BioInformatics Institute Of India – Noida
C-56 A/28, Sector -62, Noida – 201 301
www.bii.in

9. CLC bio India Pvt Ltd
#Plot No. 51, H.No. 8-3-214/51, Srinivasa Nagar (West) Ameerpet Hyderabad – 500 038
www.clcbio.com/india

10. CytoGenomics India (P) Ltd.
#3004, 12A Main HAL 2nd Stage, Bangalore 560008
www.silicocyte.com

11. Genotypic Technology
211, 6th Cross, 80ft Road, RMV II Stage, Bangalore 560094
www.genotypic.co.in

12. Genvea Biosciences
Dr. D. T. Singh, CSO, 53, Craig Rd. #04-01, Singapore-089691
www.genvea.com

13. Helix Info Systems
132 A, II Floor, Sterling Towers, IV Cross Street, Sterling Road, Nungambakkam, Chennai.
www.helixinfosystems.com

14. Jalaja Technologies Pvt. Ltd.,
21/1,Victoria Layout, Victoria Road, Bangalore-47
www.jalaja.com

15. Jubilant Biosys Ltd
#96, Industrial Subrub, 2nd Stage, Yeshwanthpur, Bangalore- 560022
Jubilant Organosys Ltd.
1A, Sector 16A, Noida – 201 301 (India)
www.jubl.com

16. Kshema Technologies
#1, Global Village, Mylasandra, Mysore Road, Bangalore-560 059.
www.mphasis.com

17. LabNetworx
B-704, Gitanjali Apartments, Vikas Marg Extension, New Delhi – 110 092
www.labnetworx.com

18. LabVantage Solutions Pvt. Ltd.
Bengal Intelligent Park, Building C, 2nd Floor, Sector V, Salt Lake Electronics Complex, Kolkata – 700 091
www.labvantage.com

19. LeadInvent, 
2nd Floor, Biotech Centre, University of Delhi, South Campus, Benito Juarez Road, New Delhi 110021, India
Contact no: +91 11 24119241
Email: contact@leadinvent.com
www.leadinvent.com

20. Mascon Life Sciences
B – 8/ 10, Vasant Vihar, New Delhi 110057, India
www.masconlifesciences.com

21. Molecular Connections P Ltd
Kandala Mansion, 2/2 Kariappa Road, Near Krishna Rao Park, Basavangudi, Bangalore – 4
www.molecularconnections.com

22.Novo Informatics Pvt. Ltd.
TBIU, 2nd Floor, Synergy Building, Indian Institute of Technology, Hauz Khas, New Delhi-16.
Contact: 91-11-26581524, 91-11-26581766(Extension: 28)
Email: info@novoinformatics.com
www.novoinformatics.com

23. Ocimum Biosolutions (India) Ltd
6th Floor, Reliance Classic, Road No.1 Banjara Hills, Hyderabad 500 034, India.
www.ocimumbio.com

24. Scube Scientific Software Solutions
613, Hemkunt Chambers, 89, Nehru Place, New Delhi -110 019
www.scribeindia.com

25. Siri Technologies Pvt Ltd.
38/C -23, South End Road, Basavanagudi, Bangalore-56004.
www.siritech.com

26. Strand Life Sciences Pvt. Ltd.
#237, Sir C. V. Raman Avenue, Raj Mahal Vilas, Bangalore 560 080 INDIA
www.strandls.com

27. SooryaKiran Bioinformatics (P) Ltd
TBIC-13, Tejaswini Building, Technopark, Thriruvananthapuram- 695 584, Keralam, India

Ph: +91 471 4060979,+91 9895404104
Email: reachus@sooryakiran.com
http://www.sooryakiran.com

28. Systat Software Asia Pacific
4th Floor, Block 1, Shankar Narayan Building, No.25, MG Road, Bangalore – 560001
www.systat.com

29. ABC Genomics (India) Pvt. Ltd.
Biotech Park, Sector G, Jankipuram, Kursi Road, Lucknow-226021, U.P., INDIA
Tel +91-522-4068579, Email: director@abcgenomics.com
www.abcgenomics.com

30. en-GENE-ier's Core Technology Services,
1/340, Virat Khand, Gomtinagar, 
(Near Maharaja Agrasen Public School)
lucknow-226010, U.P., India.
http://www.bio.egicore.com/

Best of luck for your job hunts :).

Genomes and genomics:

Bioinformatics and Genomics:

Structural genomics tutorial:

Comparative Genomics Tutorial:

GENOME TUTORIAL:

Tools and resources for identifying protein families, domains and motifs

Bioinformatics Tools 
Tips, Tutorials, and Terminology for Using Selected Resources in Genome Database Guide:

A Web-Based Comparative Genomics Tutorial for Investigating Microbial Genomes:

Free Online Tutorials Teach Anyone How to Use Genome Databases:

Circos to create concise, explanatory, unique and print-ready visualizations of your data:

Genomics and Comparative Genomics Learning Module:

Computational Challenges in Comparative Genomics

A Tutorial:

A Comparative Genomics Resource for Grains:

PLAZA: A Comparative Genomics Resource to Study Gene and Genome Evolution in Plants:

VISTA:

Software for Genomics

1. Artemis Artemis is a free genome viewer and annotation tool that allows visualization of sequence features and the results of analyses within the context of the sequence, and its six-frame translation.
2. Chromas It will display and prints chromatogram files from ABI automated DNA sequencers, and Staden SCF files which the analysis programs for ALF, Li-Cor and Visible Genetics OpenGene sequencers can create.
3. Glimmer A system for finding genes in microbial DNA, especially the genomes of bacteria and archaea.Glimmer (Gene Locator and Interpolated Markov Modeler) uses interpolated Markov models (IMMs) to identify the coding regions and distinguish them from noncoding DN
4. Glimmer HMM A fast and accurate gene finder based on a GHMM architecture, developed specifically for eukaryotes. It incorporates splice site models adapted from the GeneSplicer program and uses interpolated Markov models for evaluating the coding regions.
5. Glimmer M A gene finder derived from Glimmer, but developed specifically for eukaryotes. It is based on a dynamic programming algorithm that considers all combinations of possible exons for inclusion in a gene model and chooses the best of these combinations. The d
6. MUMmer MUMmer is a system for rapidly aligning entire genomes, whether in complete or draft form.
7. pDRAW pDRAW32 is being developed as a free time hobby project. It is far from finished, but as it has reached a point where it could be helpful for many labs, it is now available to the scientific community.
8. Sequin Sequin is a stand-alone software tool developed by the NCBI for submitting and updating entries to the GenBank, EMBL, or DDBJ sequence databases. It is capable of handling simple submissions that contain a single short mRNA sequence, and complex submissio
9. Staden The Staden Package consists of a series of tools for DNA sequence preparation (pregap4), assembly (gap4), editing (gap4) and DNA/protein sequence analysis (spin).

For more software @ http://bioinformaticsonline.com/bookmarks/view/926/list-of-popular-bioinformatics-softwaretools

Here is the list Bioinformatics courses offered around the world. Reasons for constructing this page are:

The graduate courses outlined in the table mainly exist as a coursework component of an MSc or PhD degree. Of course, many institutions will also have pure research programs in Bioinformatics at the Hons, MSc, or PhD level and will not have a 'coursework component'. These research programs may not always reflect the main research program of the institution since the research depends upon the interests of a particular individual or small team within that institution. It is difficult to track these individual research programs. Consequently, we have not included all institutions with a bioinformatics research project. Bioinformatics is an interdisciplinary subject and this is reflected in the fact that the courses are offered by departments or schools as diverse as: computer science, biochemistry, molecular biology, microbiology, engineering, and mathematics. Similarly, bioinformatics may also be known by other names such as: computational biology, biocomputing, molecular informatics, computational molecular biology, biological information theory, molecular phylogenetics, and molecular bioinformatics.

Bioinformatics University Courses

US

Canada

Europe

Sweden

Norway

*The journals are not listed in any ascending, descending, or impact factors oders. 

Bioinformatics 

Journal of Computational Biology

Briefings in Bioinformatics

In Silico Biology

Structure

Protein Science

Protein Engineering

Proteomics

Nucleic Acids Research

Trends in Biotechnology

Proceedings of the National Academy of Sciences

Folding and Design

Genome Biology

Journal of Biomedical Informatics

Bioinformation

Journal of Computational Intelligence in Bioinformatics

Journal of Structural and Functional Genomics

Journal of Molecular Graphics and Modelling

Metabolic Engineering

Computers & Chemistry

Artificial Intelligence in Medicine

Journal of Biomedical Science

Artificial Intelligence

Machine Learning

Applied Bioinformatics

Applied Genomics and Proteomics

BMC Bioinformatics

Online Journal of Bioinformatics (OJB)

PSB On-Line Proceedings

Bioinformatics: Information Technology & Systems (BITS)

Data Mining and Knowledge Discovery

The EMBO Journal

Current Opinions in Structural Biology

Journal of Molecular Microbiology and Biotechnology

Nature

Nature Structural Biology

Journal of Machine Learning Research

Nature Genetics

Current Opinion in Genetics & Development

Nature Biotechnology

Trends in Biochemical Sciences

Proteins: Structure, Function, and Genetics

Nature Cell Biology

Trends in Genetics

ChemBioChem

Trends in Molecular Medicine

Journal of Molecular Modelling

Trends in Pharmacological Sciences

Drug Discovery Today

Others Free Online Full-text Journals

The evolutionary connections between organisms are represented graphically through phylogenetic trees. Due to the fact that evolution takes place over long periods of time that cannot be observed directly, biologists must reconstruct phylogenies by inferring the evolutionary relationships among present-day organisms. 
Application of the techniques that make this possible can be seen in the very limited field of human genetics, such as the ever more popular use of genetic testing to determine a child's paternity, as well as the emergence of a new branch of criminal forensics focused on genetic evidence.
The effect on traditional scientific classification schemes in the biological sciences has been dramatic as well. Work that was once immensely labor- and materials-intensive can now be done quickly and easily, leading to yet another source of information becoming available for systematic and taxonomic appraisal. This particular kind of data has become so popular that taxonomical schemes based solely on molecular data may be encountered. Proponents even claim that taxonomy was previously based on morphology alone, which of course is utter fable.

For additional information on phylogenetics, see list of Phylogenetics Resources on the Internet.

Phylogeny and Reconstructing Phylogenetic Trees: http://aleph0.clarku.edu/~djoyce/java/Phyltree/cover.html
the CBRG and Department of Statistics Phylogeny tutorial: http://www.compbio.ox.ac.uk/tutorials/phylogeny/
TUTORIAL: PHYLOGENETIC ANALYSIS USING PARSIMONY:http://home.cc.umanitoba.ca/~psgendb/GDE/phylogeny/parsimony/phylip.parsimony.html

PHYLIP: http://www.umanitoba.ca/afs/plant_science/psgendb/doc/Phylip/main.html
An Introduction to Molecular Phylogeny: http://bibiserv.techfak.uni-bielefeld.de/gcb04/tutorials/hoef-emden/GCB04Tut.pdf

How to make a phylogenetic tree: http://www.hiv.lanl.gov/content/sequence/TUTORIALS/TREE_TUTORIAL/Treetutorial.html
Phylogenetic Trees: http://cnx.org/content/m11052/latest/
Phylogeny by Ron Shamir: http://www.cs.tau.ac.il/~rshamir/algmb/01/scribe08/lec08.pdf
Introduction to Phylogeny: http://www.utm.edu/departments/cens/biology/rirwin/391/391Phylog.htm
Lecturer notes on Phylogeny: http://www.sbc.su.se/~bens/course_material/phylocourse1/lecture2.pdf
Principles and Practice of Phylogenetic Systematics:http://www.faculty.biol.ttu.edu/Strauss/Phylogenetics/LectureNotes.htm

Inferring phylogenetic trees: http://www.cis.hut.fi/Opinnot/T-61.6070/slides2008/pres_6070.pdf

Lecture Notes

Chapter 1 - The Diversity, Classification, and Evolution of Vertebrates:http://academic.emporia.edu/mooredwi/nathist/chap1.htm

Algorithms for Phylogenetic Reconstructions:http://lectures.molgen.mpg.de/Algorithmische_Bioinformatik_WS0405/phylogeny_script.pdf

Phylogeny.fr is a free, simple to use web service dedicated to reconstructing and analysing phylogenetic relationships between molecular sequences. Phylogeny.fr runs and connects various bioinformatics programs to reconstruct a robust phylogenetic tree from a set of sequences. For more detail : http://www.phylogeny.fr/version2_cgi/index.cgi

A Brief Tutorial on Phylogenetics
http://bioss.ac.uk/~dirk/talks/tutorial_phylogenetics.pdf

A Brief Tutorial on Phylogenetics Human Rabbit Chicken
http://bioss.ac.uk/~dirk/talks/psnup_tutorial_phylogenetics.pdf

Phylogenetic Tree Computation Tutorial Overview
http://pga.lbl.gov/Workshop/April2002/lectures/Olken.pdf

MrBayes: A program for the Bayesian inference of phylogeny
http://golab.unl.edu/teaching/SBseminar/manual.pdf

Web sites providing software for the construction of phylogenetic trees

• BioEdit

• Coelocanth-Fish Out of Time

• Computational Biochemistry Research Group

• Digital Taxonomy

• Hennig 86

• Hyperclean from Bioinformatics Solutions, Inc.

• Memorial University of Newfoundland

• Mr. Bayes

• NONA

• Oxford University Evolutionary Biology Group

• Paleobiology Database

• PAUP

• Phylip Homepage

• Poy

• Sinauer Associates

• TNT-Tree Analysis Using New Technology

• Tree Base

• Treefinder

• Tree-Puzzle

• Tree View-Taxonomy and Systematics Group at Glasgow

• Washington University-List of Phylogeny Software

We use algorithms every day. For example, a recipe for baking a cake is an algorithm. Most programs, with the exception of some artificial intelligence applications, consist of algorithms. Inventing elegant algorithms -- algorithms that are simple and require the fewest steps possible -- is one of the principal challenges in programming. An algorithm is a description of a procedure which terminates with a result. In other words an algorithm is a set of instructions, sometimes called a procedure or a function, that is used to perform a certain task. This can be a simple process, such as adding two numbers together, or a complex function, such as adding effects to an image. For example, in order to sharpen a digital photo, the algorithm would need to process each pixel in the image and determine which ones to change and how much to change them in order to make the image look sharper.

In mathematics, computer science, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields.
Each algorithm is a list of well-defined instructions for completing a task. Starting from an initial state, the instructions describe a computation that proceeds through a well-defined series of successive states, eventually terminating in a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate randomness.

History

The origin of the term comes from the ancients. The concept becomes more precise with the use of variables in mathematics. Algorithm in the sense of what is now used by computers appeared as soon as first mechanical engines were invented.
The word algorithm comes from the name of the 9th century Persian Muslim mathematician Abu Abdullah Muhammad ibn Musa Al-Khwarizmi. The word algorism originally referred only to the rules of performing arithmetic using Hindu-Arabic numerals but evolved via European Latin translation of Al-Khwarizmi's name into algorithm by the 18th century. The use of the word evolved to include all definite procedures for solving problems or performing tasks.
The algorithm of Archimedes gives an approximation of the Pi number.
Eratosthenes has defined an algorithim for retrieving prime numbers.
Averroès (1126-1198) was using algorithmic methods for calculations.
Adelard de Bath (12 th) introduces the algorismus term, from Al-Khwarizmi.
During the 1800's up to the mid-1900's:

- George Boole (1847) has invented the binary algebra, the basis of computers. Actually he has unified logic and calculation in a common symbolism.

- Gottlob Frege (1879) formula language's, that is a lingua characterica, a language written with special symbols, "for pure thought", that is free from rhetorical embellishments... constructed from specific symbols that are manipulated according to definite rules.

- Giuseppe Peano (1888) It's The principles of arithmetic, presented by a new method was the first attempt at an axiomatization of mathematics in a symbolic language.

- Alfred North Whitehead and Bertrand Russell in their Principia Mathematica (1910-1913) has further simplified and amplified the work of Frege.

- Kurt Goëdel (1931) cites the paradox of the liar that completely reduces rules of recursion to numbers.

The concept of algorithm was formalized in 1936 through Alan Turing's Turing machines and Alonzo Church's lambda calculus, which in turn formed the foundation of computer science.
Stephen C. Kleene (1943) defined his now-famous thesis known as the "Church-Turing Thesis". In this context:

" Algorithmic theories... In setting up a complete algorithmic theory, what we do is to describe a procedure, performable for each set of values of the independent variables, which procedure necessarily terminates and in such manner that from the outcome we can read a definite answer, "yes" or "no," to the question, "is the predicate value true?"

Classification

Classification by purpose

Each algorithm has a goal, for example, the purpose of the Quick Sort algorithm is to sort data in ascending or descending order. But the number of goals is infinite, and we have to group them by kind of purposes:

Classification by implementation

An algorithm may be implemeted according to different basical principles.

• Recursive or iterative

A recursive algorithm is one that calls itself repeatedly until a certain condition matches. It is a method common to functional programming. 
Iterative algorithms use repetitive constructs like loops.
Some problems are better suited for one implementation or the other. For example, the towers of hanoi problem is well understood in recursive implementation. Every recursive version has an iterative equivalent iterative, and vice versa.

• Logical or procedural

An algorithm may be viewed as controlled logical deduction. 
A logic component expresses the axioms which may be used in the computation and a control component determines the way in which deduction is applied to the axioms. 
This is the basis of the logic programming. In pure logic programming languages the control component is fixed and algorithms are specified by supplying only the logic component.

• Serial or parallel

Algorithms are usually discussed with the assumption that computers execute one instruction of an algorithm at a time. This is a serial algorithm, as opposed to parallel algorithms, which take advantage of computer architectures to process several instructions at once. They divide the problem into sub-problems and pass them to several processors. Iterative algorithms are generally parallelizable. Sorting algorithms can be parallelized efficiently.

• Deterministic or non-deterministic

Deterministic algorithms solve the problem with a predefined process whereas non-deterministic algorithm must perform guesses of best solution at each step through the use of heuristics.

Classification by design paradigm

A design paradigm is a domain in research or class of problems that requires a dedicated kind of algorithm:

• Divide and conquer

A divide and conquer algorithm repeatedly reduces an instance of a problem to one or more smaller instances of the same problem (usually recursively), until the instances are small enough to solve easily. One such example of divide and conquer is merge sorting. Sorting can be done on each segment of data after dividing data into segments and sorting of entire data can be obtained in conquer phase by merging them.
The binary search algorithm is an example of a variant of divide and conquer called decrease and conquer algorithm, that solves an identical subproblem and uses the solution of this subproblem to solve the bigger problem.

• Dynamic programming

The shortest path in a weighted graph can be found by using the shortest path to the goal from all adjacent vertices. 
When the optimal solution to a problem can be constructed from optimal solutions to subproblems, using dynamic programming avoids recomputing solutions that have already been computed. 
- The main difference with the "divide and conquer" approach is, subproblems are independent in divide and conquer, where as the overlap of subproblems occur in dynamic programming. 
- Dynamic programming and memoization go together. The difference with straightforward recursion is in caching or memoization of recursive calls. Where subproblems are independent, this is useless. By using memoization or maintaining a table of subproblems already solved, dynamic programming reduces the exponential nature of many problems to polynomial complexity.

• The greedy method

A greedy algorithm is similar to a dynamic programming algorithm, but the difference is that solutions to the subproblems do not have to be known at each stage. Instead a "greedy" choice can be made of what looks the best solution for the moment. 
The most popular greedy algorithm is finding the minimal spanning tree as given by Kruskal.

• Linear programming

The problem is expressed as a set of linear inequalities and then an attempt is made to maximize or minimize the inputs. This can solve many problems such as the maximum flow for directed graphs, notably by using the simplex algorithm. 
A complex variant of linear programming is called integer programming, where the solution space is restricted to all integers.

• Reduction also called transform and conquer

Solve a problem by transforming it into another problem. A simple example: finding the median in an unsorted list is first translating this problem into sorting problem and finding the middle element in sorted list. The main goal of reduction is finding the simplest transformation possible.

• Using graphs

Many problems, such as playing chess, can be modeled as problems on graphs. A graph exploration algorithms are used. 
This category also includes the search algorithms and backtracking.

The probabilistic and heuristic paradigm

• Probabilistic

Those that make some choices randomly.

• Genetic

Attempt to find solutions to problems by mimicking biological evolutionary processes, with a cycle of random mutations yielding successive generations of "solutions". Thus, they emulate reproduction and "survival of the fittest".

• Heuristic

Whose general purpose is not to find an optimal solution, but an approximate solution where the time or resources to find a perfect solution are not practical.

Classification by complexity

Some algorithms complete in linear time, and some complete in exponential amount of time, and some never complete.

Algorithms resources on net.

Graph Algorithms in Bioinformatics

Bioinformatics Algorithms Description

Bioinformatics Algorithms Course Page

Bioinformatics Algorithm Demonstrations

Introduction to Bioinformatics Algorithms Lectures 1-2 by Dr. Max Alekseyev USC, 2009

Online Lectures on Bioinformatics

Sequence Alignment Algorithms

Algorithm for sequence alignment: dynamic programming

Network Protocol Analysis using Bioinformatics Algorithms

Bioinformatics Algorithms Links

Dynamic Programming

Particularly good sites...

•http://www.cis.upenn.edu/~sahuguet/MSA/
•http://www.blc.arizona.edu/courses/bioinformatics/align.html
•http://www.cs.monash.edu.au/~lloyd/tildeStrings/Notes/DPA.html
•http://www.cs.orst.edu/~schut/cs325/dynamic.htm
•http://www.catalase.com/dprog.htm
•http://bioweb.ncsa.uiuc.edu/~bioph490/BIOPH2.html#SEQUENCE_COMP
•http://www.qucis.queensu.ca/home/cisc365/javascript/dp1/index.html
Other sites...
•http://bioweb.ncsa.uiuc.edu/~bioph490/dynamic_programming_demo.html
•http://www.qucis.queensu.ca/home/cisc365/365overheads.html
•http://www.qucis.queensu.ca/home/cisc365/dp/dp.p01.html
•http://www.dgp.toronto.edu/csc270/tut_dp.html
•http://queue.ieor.berkeley.edu/~jshu/knapsack/DP/dp.html
•http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html
•http://www.cs.sandia.gov/~scistra/class_3
•http://levine.sscnet.ucla.edu/Econ101/dynamic.htm
•http://mat.gsia.cmu.edu/classes/stoch_dynamic/stoch_dynamic.html
•http://mat.gsia.cmu.edu/classes/dynamic/node8.html
•http://www.maths.mu.oz.au/~moshe/dp/bibl/bibliography.html
•http://cartan.gmd.de/PAPER/ismb95/ismb_html.html
•http://screwdriver.bu.edu/bibliography/dynamic_programming.htm
•http://www.norvig.com/design-patterns/
•http://tome.cbs.univ-montp1.fr/htmltxt/Doc/manual/node137.html
•http://poem.princeton.edu/~verdu/dynamic.html
•http://www.orca1.com/opushelpweb/opusDynamic_Programming.html
•http://screwdriver.bu.edu/cn760-lectures/l7/index.htm
•http://www.ms.unimelb.edu.au/~moshe/dp/dp.html
•http://mat.gsia.cmu.edu/ORCS/0255.html
•http://aae.wisc.edu/e703/notes/a13dynpr.htm
•http://bioweb.pasteur.fr/docs/modeller/node137.html
•http://www2.uwindsor.ca/~lama/my470/ddynamic.htm
•http://students.ceid.upatras.gr/~papagel/project/ex5_6_1.htm
•http://www.cs.sunysb.edu/~algorith/lectures-good/node12.html
•http://www.cs.sunysb.edu/~algorith/lectures-good/node12.html
•http://www.utdallas.edu/~scniu/documents/7315.htm
•http://www.ii.uib.no/~pinar/seminar/larry.html
•http://www.deakin.edu.au/~gecole/books.html
•http://www.cseg.engr.uark.edu/~wessels/algs/notes/dynamic.html
•http://www.csc.liv.ac.uk/~ped/teachadmin/algor/dyprog.html
•http://www.eli.sdsu.edu/courses/fall96/cs660/notes/dynamicProg/dynamicProg.html
•http://www.cs.indiana.edu/l/www/ftp/techreports/TR514.html
•http://www.cs.brandeis.edu/~mairson/poems/node3.html
•http://www.cis.tu-graz.ac.at/igi/oaich/animations/Dynamic2.html
•http://bioweb.ncsa.uiuc.edu/~workshop/

Smith Waterman
•http://genome-www.stanford.edu/Saccharomyces/help/sw_alignment.html
•http://genome-www.stanford.edu/Saccharomyces/help/sw_details.html
•http://www.stanford.edu/~sntaylor/bioc218/final.htm
•http://www.maths.tcd.ie/~lily/pres2/sld009.htm
•http://bioweb.ncsa.uiuc.edu/~workshop/Lab_3/Smith-Waterman.htm
•http://www.tigem.it/LOCAL/SW/threshold.html
•http://sgbcd.weizmann.ac.il/genweb/help/smith-waterman.html
•http://cbrg.ethz.ch/ServerBooklet/section2_3_5.html
Needleman & Wunsch
•http://www.maths.tcd.ie/~lily/pres2/sld003.htm
•http://acer.gen.tcd.ie/~amclysag/nwswat.html
•http://www.nada.kth.se/~erikw/thesis/chapter2_3.html
•http://www.irbm.it/irbm-course95/gb/docs/amps/subsection3_6_1.html
•http://www.ibc.wustl.edu/~zuker/Bio-5495/align-html/node3.html

General (NW vs. SW vs. HMM, etc.)

•http://www.maths.tcd.ie/~lily/pres2/
•http://acer.gen.tcd.ie/~amclysag/nwswat.html
•http://laguerre.psc.edu/biomed/TUTORIALS/SEQUENCE/MULTIPLE/tutorial.html
•http://www.cse.ucsc.edu/research/compbio/

Hmms

•http://www.medmicro.mds.qmw.ac.uk/HMMER/main.html
•http://alfredo.wustl.edu/ismb96/abs/p02.html
•http://www.cse.ucsc.edu/research/compbio/html_format_papers/hughkrogh96/cabios.html
•http://wwwsyseng.anu.edu.au/~jason/hmmlinks.html
•http://www.breadfan.com/markov.html
•http://cslu.cse.ogi.edu/HLTsurvey/ch1node34.html
•http://www.ibc.wustl.edu/service/hmmalign/glocal.html
•http://www.cse.ucsc.edu/research/compbio/html_format_papers/ismb94/node5.html
•http://www.iscs.nus.edu.sg/~luakt/ic3222/lecture/nlp18new/index.htm
•http://www.cse.ucsc.edu/research/compbio/sam.html SAM Software for HMMs

Genetic Algorithms

•http://www.staff.uiuc.edu/~carroll/ga.html
•http://kal-el.ugr.es/gags.html
•http://kal-el.ugr.es/~jmerelo/GAJS.html
•http://www.genetic-programming.org/
•http://www.iitk.ac.in/kangal/deb_tut.shtml

Data mining commonly involves four classes of tasks:

• Classification - Arranges the data into predefined groups. For example, an email program might attempt to classify an email as legitimate or spam. Common algorithms include decision tree learning, nearest neighbor, naive Bayesian classification and neural networks.
• Clustering - Is like classification but the groups are not predefined, so the algorithm will try to group similar items together.
• Regression - Attempts to find a function which models the data with the least error.
• Association rule learning - Searches for relationships between variables. For example a supermarket might gather data on customer purchasing habits. Using association rule learning, the supermarket can determine which products are frequently bought together and use this information for marketing purposes. This is sometimes referred to as market basket analysis.
• From experience, I can say that is one of the most frustrating positions to be in. Data mining is a huge field and can easily be bewildering for a beginner. However, high through-put techniques in molecular biology require, more and more, that bioinformatics is required to interpret the data. Furthermore, people working in bioinformatics generally come from computer science, or biology backgrounds. Data mining, however, involves statistics to one degree or another, which means entering a field that is may not be your strong point.
• Excel is fine for creating graphs. If you’re serious about data mining though, you’ll need something more heavy weight. I use R, free, and with good data mining packages such as vegan and labdsv. For beginners R can be impenetrable, I recommend this book an introduction to R as well as the underlying statistics.
• Any of us can rush head on into a land of support vector machines, hidden markov models and neural networks. But coming back to the first point, what are you trying to prove? Always question what are you doing, how does it fit in to the wider picture? Try to regularly review, and keep track of where you are going? This will prevent you from falling into data mining despair.

Data Mining Resources on the net:

A laboratory of data mining and bioinformatics is headed by Prof. Ambuj Singh. There are currently seven graduate students in the research group. Our research focuses on image informatics and scalable querying and mining of graphs.For more detail visit: http://www.cs.ucsb.edu/~dbl/

Here are the materials (Lecture notes) from several past courses on data mining and/or Web mining by Stanford: For detail visit: http://infolab.stanford.edu/~ullman/mining/mining.html
Statistical Data Mining Tutorial Slides by Andrew Moore The following links point to a set of tutorials on many aspects of statistical data mining, including the foundations of probability, the foundations of statistical data analysis, and most of the classic machine learning and data mining algorithms. For detail visit: http://www.autonlab.org/tutorials/

A tutorial on Introduction to Data Mining for Discovering hidden value in your data warehouse:http://www.thearling.com/text/dmwhite/dmwhite.htm 
Wiki Links: http://en.wikipedia.org/wiki/Data_mining
Bioinformatics with Clementine http://www.spss.ch/upload/1051192224_inseratClemBio.pdf 
Causal Data Mining in Bioinformatics by Ioannis Tsamardinos: http://www.forth.gr/ics/bmi/In_the_News/2007/EN69-4.pdf

Report on ACM Text Mining in Bioinformatics (TMBIO 006) http://www.sigir.org/forum/2007J/2007j_sigirforum_song.pdf 
BIOKDD 2002: Recent Advances in Data Mining for 
Bioinformatics: http://www.acm.org/sigs/sigkdd/explorations/issue4-2/zaki.pdf

Bioinformatics and Medical Informatics: 

Tools for Mining and Applying Genetic Information in Patient Care:http://www.biomedtechalliance.org/pdfs/03_03_05/03_03_05.pdf

DATA MINING OF MICROARRAY DATABASES FOR HUMAN LUNG CANCER: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.385&rep=rep1&type=pdf

Towards knowledge-based gene expression data mining: http://www.ailab.si/blaz/papers/2007-JBI-BellazziZupan.pdf

DRAFT Accepted for publication in 'Data Mining in Bioinformatics'
Jason Wang, Mohammed Zaki, Hannu Toivonen, and Dennis Shasha (Eds.), Springer:http://www.cs.helsinki.fi/u/htoivone/pubs/gene_mapping_by_pattern_discovery.pdf

Data Mining and Text Mining for Bioinformatics: Proceedings of the European Workshop: http://www.rok.informatik.hu-berlin.de/wbi/research/publications/2003/proceedings_ws_mining.pdf

Biological Network Analysis:

Graph Mining in Bioinformatics: http://agbs.kyb.tuebingen.mpg.de/wikis/bg/BNA-5.pdf.

Text mining in bioinformatics: http://agbs.kyb.tuebingen.mpg.de/wikis/bg/4.pdf

Some datamining books that are available on google books:

Data mining and bioinformatics: first international workshop, VDMB 2006 By Mehmet M. Dalkilic

Data mining: concepts and techniques By Jiawei Han, Micheline Kamber

"The mathematical, statistical and computing methods that aim to solve biological problems using DNA and amino acid sequences and related information."

"The collection, organization and analysis of large amounts of biological data, using networks of computers and databases." - from the glossary for ABC Science Online's feature: The State of the Genome 2001.

"It is defined here as an interdisciplinary research area that applies computer and information science to solve biological problems. However, this is not the only definition. The field is being defined (and redefined) at present, and there are probably as many definitions as there are bioinformaticians (bioinformaticists?).

The following references are a snapshot of the moving target named bioinformatics. ... " - from the University of Minnesota Graduate Program in Bioinformatics' page: What is Bioinformatics,

"The application of computer technology to the management of biological information.Bioinformatics uses computers to solve problems in the life sciences, such as determination of DNA and protein sequences, investigation of protein functions, development of pharmaceuticals. It involves the creation of extensive electronic databases on genomes and protein sequences, and techniques such as the three-dimensional modeling of biomolecules and biologic systems. ..." - from the Bioinformatics Glossary edited by Charles E. Kahn, Jr., Medical College of Wisconsin.

"Bioinformatics is the field of science in which biology, computer science, and information technology merge to form a single discipline. The ultimate goal of the field is to enable the discovery of new biological insights as well as to create a global perspective from which unifying principles in biology can be discerned." - from the National Center for Biotechnology Information's Bioinformatics Factsheet.

"Research, development, or application of computational tools and approaches for expanding the use of biological, medical, behavioral or health data, including those to acquire, store, organize, archive, analyze, or visualize such data." - NIH Bioinformatics Web site

"The use of computers, laboratory robots and software to create, manage and interpret massive sets of complex biological data." - from the glossary for the University of Michigan Health System's Symphony of Life: Genetics & Medicine Web site.

"The field of science in which biology, computer science, and information technology merge into a single discipline.There are three important sub-disciplines within bioinformatics: (1) the development of new algorithms and statistics with which to assess relationships among members of large data sets; (2) the analysis and interpretation of various types of data including nucleotide and amino acid sequences, protein domains, and protein structures; and (3) the development and implementation of tools that enable efficient access and management of different types of information." - U.S. Environmental Protection Agency's ComputationalToxicology Research Glossary.

What is Bioinformatics? "One idea for a definition: (Molecular) Bio - informatics = is conceptualizing biology in terms of molecules (in the sense of physical-chemistry) and then applying "informatics" techniques (derived from disciplines such as applied math, CS, and statistics) to understand and organize the information associated with these molecules, on a large-scale." - By Mark Gerstein, Gerstein Group - Yale Bioinformatics.

Bioinformatics

Definition:

Bioinformatics derives knowledge from computer analysis of biological data. These can consist of the information stored in the genetic code, but also experimental results from various sources, patient statistics, and scientific literature. Research in bioinformatics includes method development for storage, retrieval, and analysis of the data. Bioinformatics is a rapidly developing branch of biology and is highly interdisciplinary, using techniques and concepts from informatics, statistics, mathematics, chemistry, biochemistry, physics, and linguistics. It has many practical applications in different areas of biology and medicine.

Description:

The history of computing in biology goes back to the 1920s when scientists were already thinking of establishing biological laws solely from data analysis by induction (e.g. A.J. Lotka, Elements of Physical Biology, 1925). However, only the development of powerful computers, and the availability of experimental data that can be readily treated by computation (for example, DNA or amino acid sequences and three–dimensional structures of proteins) launched bioinformatics as an independent field. Today, practical applications of bioinformatics are readily available through the world wide web, and are widely used in biological and medical research. As the field is rapidly evolving, the very definition of bioinformatics is still the matter of some debate.

The relationship between computer science and biology is a natural one for several reasons. First, the phenomenal rate of biological data being produced provides challenges: massive amounts of data have to be stored, analysed, and made accessible. Second, the nature of the data is often such that a statistical method, and hence computation, is necessary. This applies in particular to the information on the building plans of proteins and of the temporal and spatial organisation of their expression in the cell encoded by the DNA. Third, there is a strong analogy between the DNA sequence and a computer program (it can be shown that the DNA represents a Turing Machine).

Analyses in bioinformatics focus on three types of datasets: genome sequences, macromolecular structures, and functional genomics experiments (e.g. expression data, yeast two–hybrid screens). But bioinformatic analysis is also applied to various other data, e.g. taxonomy trees, relationship data from metabolic pathways, the text of scientific papers, and patient statistics. A large range of techniques are used, including primary sequence alignment, protein 3D structure alignment, phylogenetic tree construction, prediction and classification of protein structure, prediction of RNA structure, prediction of protein function, and expression data clustering. Algorithmic development is an important part of bioinformatics, and techniques and algorithms were specifically developed for the analysis of biological data (e.g., the dynamic programming algorithm for sequence alignment).

Bioinformatics has a large impact on biological research. Giant research projects such as the human genome project [4] would be meaningless without the bioinformatics component. The goal of sequencing projects, for example, is not to corroborate or refute a hypothesis, but to provide raw data for later analysis. Once the raw data are available, hypotheses may be formulated and tested in silico. In this manner, computer experiments may answer biological questions which cannot be tackled by traditional approaches. This has led to the founding of dedicated bioinformatics research groups as well as to a different work practice in the average bioscience laboratory where the computer has become an essential research tool.

Three key areas are the organisation of knowledge in databases, sequence analysis, and structural bioinformatics.

Organizing biological knowledge in databases:

Biological raw data are stored in public databanks (such as Genbank or EMBL for primary DNA sequences). The data can be submitted and accessed via the world wide web. Protein sequence databanks like trEMBL provide the most likely translation of all coding sequences in the EMBL databank. Sequence data are prominent, but also other data are stored, e. g. yeast two–hybrid screens, expression arrays, systematic gene–knock–out experiments, and metabolic pathways.

The stored data need to be accessed in a meaningful way, and often contents of several databanks or databases have to be accessed simultaneously and correlated with each other. Special languages have been developed to facilitate this task (such as the Sequence Retrieval System (SRS) and the Entrez system). An unsolved problem is the optimal design of inter–operating database systems. Databases provide additional functionality such as access to sequence homology searches and links to other databases and analysis results. For example, SWISSPROT [1] contains verified protein sequences and more annotations describing the function of a protein. Protein 3D structures are stored in specific databases (for example, the Protein Data Bank [2], now primarily curated and developed by the Research Collaboratory for Structural Bioinformatics). Organism specific databases have been developed (such as ACEDB, the A C. Elegans DataBase for the C. elegans genome, FLYBASE for D. melanogaster etc). A major problem are errors in databanks and databases (mostly errors in annotation), in particular since errors propagate easily through links.

Also databases of scientific literature (such as PUBMED, MEDLINE) provide additional functionality, e.g. they can search for similar articles based on word–usage analysis. Text recognition systems are being developed that extract automatically knowledge about protein function from the abstracts of scientific articles, notably on protein–protein interactions.

Analysing sequence data:

The primary data of sequencing projects are DNA sequences. These become only really valuable through their annotation. Several layers of analysis with bioinformatics tools are necessary to arrive from a raw DNA sequence at an annotated protein sequences:

• establish the correct order of sequence contigs to obtain one continuous sequence;
• find the tranlation and transcription initiation sites, find promoter sites, define open reading frames (ORF);
• find splice sites, introns, exons;
• translate the DNA sequence into a protein sequence, searching all six frames;
• compare the DNA sequence to known protein sequences in order to verify exons etc with homologuous sequences.

Some completely automated annotation systems have been developed (e.g., GENEQUIZ), which use a multitude of different programs and methods.

The protein sequences are further analysed to predict function. The function can often be inferred if a sequence of a homologous protein with known function can be found. Homology searches are the predominant bioinformatics application, and very efficient search methods have been developed [3]. The often difficult distinction between orthologous sequences and paralogous sequences facilitates the functional annotation in the comparison of whole genomes. Several methods detect glycolysation, myristylation and other sites, and the prediction of signal peptides in the amino acid sequence give valuable information about the subcellular location of a protein.

The ultimate goal of sequence annotation is to arrive at a complete functional description of all genes of an organism. However, function is an ill–defined concept. Thus, the simplified idea of “one gene – one protein – one structure – one function” cannot take into account proteins that have multiple functions depending on context (e.g., subcellar location and the presence of cofactors). Well-known cases of “moonlighting” proteins are lens crystalline and phosphoglucose isomerase. Currently, work on ontologies is under way to explicitly define a vocabulary that can be applied to all organisms even as knowledge of gene and protein roles in cells is accumulating and changing.

Families of similar sequences contain information on sequence evolution in the form of specific conservation patters at all sequence positions. Multiple sequence alignments are useful for

• building sequence profiles or Hidden Markov Models to perform more sensitive homology searches. A sequence profile contains information about the variability of every sequence position. improving structure prediction methods (secondary structure prediction). Sequence profile searches have become readily available through the introduction of PsiBLAST [3];
• studying evolutionary aspects, by the construction of phylogenetic trees from the pairwise differences between sequences: for example, the classification with 70S, 30S RNAs established the separate kingdom of archeae;
• determining active site residues, and residues specifc for subfamilies;
• predicting protein–protein interactions;
• analysing single nucleotide polymorphisms to hunt for genetic sources of deseases.
• Many complete genomes of microorganisms and a few of eukaryotes are available [4]. By analysis of entire genome sequences a wealth of additional information can be obtained. The complete genomic sequence contains not only all protein sequences but also sequences regulating gene expression. A comparison of the genomes of genetically close organisms reveals genes responsible for specific properties of the organisms (e.g., infectivity). Protein interactions can be predicted from conservation of gene order or operon organisation in different genomes. Also the detection of gene fusion and gene fission (i.e, one protein is split into two in another genome) events helps to deduce protein interactions.

Structural bioinformatics:

This branch of bioinformatics is concerned with computational approaches to predict and analyse the spatial structure of proteins and nucleic acids. Whereas in many cases the primary sequence uniquely specifies the three–dimensional (3D) structure, the specific rules are not well understood, and the protein folding problem remains largely unsolved. Some aspects of protein structure can already be predicted from amino acid content. Secondary structure can be deduced from the primary sequence with statistics or neural networks. When using a multiple sequence alignment, secondary structure can be predicted with an accuracy above 70 %.

3D models can be obtained most easily if the 3D structure of a homologous protein is known (homology modelling, comparative modelling). A homology model can only be as good as the sequence alignment: whereas protein relationships can be detected at the 20% identity level and below, a correct sequence alignment becomes very difficult, and the homology model will be doubtful. From 40 to 50% identity the models are usually mostly correct; however, it is possible to have 50% identity between two carefully designed protein sequences with different topology (the so –called JANUS protein). Remote relationships that are undetectable by sequence comparisons may be detected by sequence–to–structure–fitness (or threading) approaches: the search sequence is systematically compared to all known protein structures. Ab initio predictions of protein 3D structure remains the major challenge; some progress has been made recently by combining statistical with force–field based approaches.

Membrane proteins are interesting drug targets. It is estimated that membrane receptors form 50 % of all drug targets in pharmacological research. However, membrane proteins are underrepresented in the PDB structure database. Since membrane proteins are usually excluded from structural genomics initiatives due to technical problems, the prediction of transmembrane helices and solvent accessibility is very important. Modern methods can predict transmembrane helices with a reliability greater than 70 %.

Understanding the 3D structure of a macromolecule is crucial for understanding its function. Many properties of the 3D structure cannot be deduced directly from the primary sequence. Obtaining better understanding of protein function is the driving force behind structural genomics efforts, which can be thus understood as part of functional genomics. Similar structure can imply similar function. General structure–to–function relationships can be obtained by statistical approaches, for example, by relating secondary structure to known protein function or surface properties to cell location.

The increased speed of structure determination necessary for the structural genomics projects make an independent validation of the structures (by comparison to expected properties) particularly important. Structure validation helps to correct obvious errors (e.g., in the covalent structure) and leads to a more standardized representation of structural data, e.g., by agreeing on a common atom name nomenclature. The knowledge of the structure quality is a prerequisite for further use of the structure, e.g in molecular modelling or drug design.

In order to make as much data on the structure and its determination available in the databases, approaches for automated data harvesting are being developed. Structure classification schemes, as implemented for example in the SCOP, CATH, and FSSP databases, elucidate the relationship between protein folds and function and shed light on the evolution of protein domains.

Combined analysis of structural and genomic data will certainly get more important in the near future. Protein folds can be analysed for whole genomes. Protein–protein interactions predicted on the sequence level, can be studied in more detail on the structure level. Single Nucleotide Polymorphisms can be mapped on 3D structures of proteins in order to elucidate specific structural causes of disease.

More detailed aspects of protein function can be obtained also by force–field based approaches. Whereas protein function requires protein dynamics, no experimental technique can observe it directly on an atomic scale, and motions have to be simulated by molecular dynamics (MD) simulations. Also free energy differences (for example between binding energies of different protein ligands) can be characterized by MD simulations. Molecular mechanics or molecular dynamics based approaches are also necessary for homology modelling and for structure refinement in X–ray crystallography and NMR structure determination.

Drug design exploits the knowledge of the 3D structure of the binding site (or the structure of the complex with a ligand) to construct potential drugs, for example inhibitors of viral proteins or RNA. In addition to the 3D structure, a force field is necessary to evaluate the interaction between the protein and a ligand (to predict binding energies). In virtual screening, a library of molecules is tested on the computer for their capacities to bind to the macromolecule.

Pharmacological Relevance:

Many aspects of bioinformatics are relevant for pharmacology. Drug targets in infectious organisms can be revealed by whole genome comparisons of infectious and non–infectious organisms. The analysis of single nucleotide polymorphisms reveals genes potentially responsible for genetic deseases. Prediction and analysis of protein 3D structure is used to develop drugs and understand drug resistance.

Patient databases with genetic profiles, e.g. for cardiovascular diseases, diabetes, cancer, etc. may play an important role in the future for individual health care, by integrating personal genetic profile into diagnosis, despite obvious ethical problems. The goal is to analyse a patient’s individual genetic profile and compare it with a collection of reference profiles and other related information. This may improve individual diagnosis, prophylaxis, and therapy.

References:

Bairoch A, Apweiler R (2000) The SWISS–PROT protein sequence database and its supplement TrEMBL in 2000. Nucleic Acids Res. 28:45–48
Berman HM, Westbrook J, Feng Z, Gilliland G, Bhat TN, Weissig H, Shindyalov IN, Bourne PE (2000) The Protein Data Bank. Nucleic Acids Res. 28:235–42
Altschul SF, Madden TL, Schaffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ (1997) Gapped BLAST and PSI–BLAST: a new generation of protein database search programs. Nucleic Acids Res. 25:3389–3402
Pearson WR (2000) Flexible sequence similarity searching with the FASTA3 program package. Methods Mol. Biol. 132:185–219
The Genome International Sequencing Consortium (2001) Initial sequencing and analysis of the human genome. Nature 409:860–921
JC Venter et al. (2001) The sequence of the human genome. Science 291:1304–1351
R.D. Fleischmann et al. (1995) Whole–genome random sequencing and assembly of haemophilus–influenzae. Science 269:496–51