## 2 The biological problems
### Genetics and evolution  
The gene is the unit of heredity, and, together with many other such units, it is transmitted from parents to offspring. Each gene, acting either alone or with other genes, is responsible of one or more characteristics of the resulting organism. The human genome is estimated to comprise about \(50,000\) genes, whose size ranges from a thousand to hundreds of thousands of base pairs. The genes occur, over 23 pairs of chromosomes, at specific positions called _loci_. The characteristics controlled by the genes are an example of _polymorphic_ traits (or _polymorphisms_), i.e., traits that can take on different values, thus accounting for the large variability in the forms of life. For a simple example, assume that \(G_{1}\) is a gene responsible for the color of a plant's flowers, and another gene \(G_{2}\) determines the plant's height. The possible values for \(G_{1}\) and \(G_{2}\) are called _alleles_. For instance, it could be \(G_{1}\in\{\mathrm{yellow,red,blue}\}\), and \(G_{2}\in\{\mathrm{short,tall}\}\) so that six types of plants, with respect to these characteristics, are possible. In diploid organisms, for each gene on one chromosome, there is a corresponding similar gene on the homologous chromosome. The two copies of a gene can present the same allele on both chromosomes, or different alleles. In the first case we say the individual is _homozygous_ for that gene, while in the second we say the individual is _heterozygous_. When an individual is heterozygous, it may be the case that one particular allele is expressed, while the other is overshadowed by the first. The former type of trait is then called _dominant_, and the latter is _receive_. Referring to our previous example, if a plant is heterozygous for gene \(G_{1}\), with alleles \((\mathrm{red},\mathrm{blue})\), and red is dominant over blue, the plant will have red flowers. Gene contents are not the only type of polymorphisms. In fact, any variability in the content of a genomic region within a population is a polymorphism (although it may not be as readily observable as, e.g., the color of a plant's flowers). The smallest polymorphism at the genome level is the _single nucleotide polymorphism_ (SNP). A SNP is a locus of a specific nucleotide showing a statistically significant variability within a population. Besides very rare exceptions, at each SNP site we observe only two alleles (out of the possible four, A, T, C and G). The recent completion of the sequencing phase of the Human Genome Project has shown the vast majority of polymorphisms in humans are in fact SNPs, occurring, on average, one in each thousand bases. For a given SNP, an individual can be either homozygous or heterozygous. The values of a set of SNPs on a particular chromosome copy define a _haplotype_. In Fig. 2, we illustrate a simplistic example of three individuals and four SNPs. The alleles for SNP 1, in this example, are C and G. Individual 1, in this example, is heterozygous for SNPs 1, 2 and 3, and homozygous for SNP 4. His haplotypes are CCCT and GAGT. _Haplotyping_ an individual consists of determining his two haplotypes, for a given chromosome. With the larger availability in SNP genomic data, recent years have seen the birth of a set of new computational problems related to haplotyping. These problems are motivated by the fact that it is economically infeasible to determine the haplotypes experimentally. On the other hand, there is a cheap experiment which can determine the (less informative and often ambiguous) _genotypes_, from which the haplotypes must then be retrieved computationally. A _genotype_ provides, for an individual, information about the multiplicity of each SNP allele: i.e., for each SNP site, the genotype specifies if the individual is heterozygous or homozygous (in the latter case, it also specifies the allele). The ambiguity comes from heterozygous sites, since, to retrieve the haplotypes, one has to decide how to distribute the two allele values on the two chromosome copies (a problem also called _phasing_ the alleles).