## 2 The biological problems
### Proteins  
A protein is a large molecule, consisting of one or more chains of _aminoacids_. The aminoacid order is specified the sequence of nucleotides in the gene coding for the protein. There exist 20 aminoacids, each of which is identified by some triplets of DNA letters. The DNA triplets are called _codons_ and the correspondence of codons and aminoacids is known as the _genetic code_. Since there are \(4^{3}=64\) possible triplets of nucleotides, most aminoacids are coded by more than one triplet (called _synonyms_ for that aminoacid). For example, the aminoacid Proline (Pro) is represented by the four triplets CCT, CCC, CCA and CCG. The substitution of even a single aminoacid in a protein can have deadly effects (for instance, the mortal disease of sickle-cell anemia is caused by the alteration of one aminoacid in the gene coding for hemoglobin). The existence of synonyms, thus, reduces the probability that random mutations of some nucleotide can cause harmful effects. In order to build a protein, the DNA from a gene is first copied onto the single-stranded _messenger RNA_, denoted by mRNA. This process is termed _transcription_. Only exons are copied, while the introns are spliced out from the molecule. RNA is basically the same molecule than DNA, with the small exception that the nucleotide Thymine (T) is replaced by the an equivalent nucleotide, Uracile (U). The mRNA, which serves as a template for the protein synthesis, moves out of the nucleus into the cytoplasm, where some cellular components named _ribosomes_ read its triplets sequentially, identify the corresponding aminoacids and link them in the sequence giving rise to the protein. The process of translation of genes into proteins, requires the presence of signals to identify the beginning and the end of each information coding region (_start codons_ and _stop codons_). Being single-stranded, the mRNA can self-hybridize, and lead to the so-called _RNA structure_. As an example, consider the following RNA sequence, \(S=\texttt{UCGUGCGGUAACUUCCACGA}\). Since the two ends of \(S\) are self-complementary, part of the sequence may self-hybridize, leading to the formation of a _loop_, illustrated below: \begin{tabular}{c c} G & G \\ C & U \\ U C G U & A \\ A G C A & A \\ C & C \\ U & U \\ \end{tabular}   
Once built, by chaining the sequence of its aminoacids as specified by the mRNA, the protein immediately folds into its peculiar, and unique, three-dimensional (3D) shape. This shape is also called the _native fold_ of the protein. The 3D structure is perhaps the most important of all protein's features, since it determines completely how the protein functions and interacts with other molecules. Most biological mechanisms at the protein level are based on shape-complementarity, so that proteins present particular concavities and convexities that allow them to bind to each other and form complex structures, such as skin, hair and tendon. For this reason, for instance, drug design consists primarily in the discovery of ad-hoc peptides whose 3D shape allows them to \"dock\" onto some specific proteins and enzymes, to inhibit or enhance their function. Two typical problems related with protein structure are _Fold Prediction_ and _Fold Comparison_. The former problem consists in trying to determine the 3D structure of a protein from its aminoacid sequence. It is a problem of paramount importance for its many implications to, e.g., medicine, genetic engineering, protein classification and evolutionary studies. The latter problem is required for (i) function determination of proteins of known structure; (ii) protein clustering and classification (iii) evaluation of fold prediction. The evaluation of fold prediction is also called \"model assessment problem\", and can be stated as follows: Given a set of \"tentative\" folds for a protein (determined by biologists with the help of computer programs), and a \"correct\" one (determined experimentally, by _X-ray crystallography_ or _Nuclear Magnetic Resonance_), which of the guesses is the most correct?