## 2 The biological problems
### Genetics and evolution
Figure 2: The haplotypes of 3 individuals, with 4 SNPs. **Problem area # 4:** Haplotyping. _Reconstruction and/or correction of haplotypes from partial haplotype fragments or from genotype data. Analysis of resulting haplotypes and correlation with genetic diseases._  
Evolution.A branch of genetics known as evolutionary genetics, studies genomic changes that have occurred over long periods of time. For such changes the effects are so dramatic that they give rise to different families within species, or possibly completely new species. The main data structure used to represent evolutionary relationships is the _phylogenetic tree_, illustrated in Figure 3.  
At each branching point in the tree we associate one or more \"evolutionary events\" which are mutations in the genome of one species resulting in descendants of new species. An important class of these mutations are the so called _genome rearrangements_. These are simply misplacements of large DNA regions, such as deletions, duplications, transpositions, inversions, and translocations. These events affect a long fragment of DNA on a chromosome. In a deletion the fragment is simply removed from the chromosome. A duplication creates many copies of the fragment, and inserts them in different positions, on the same chromosome. When an inversion or a transposition occurs, the fragment is detached from its original position and then is reinserted, on the same chromosome. In an inversion, it is reinserted at the same place, but with opposite orientation than it originally had. In a transposition, it keeps the original orientation but ends up in a different position. Finally, a translocation causes a pair of fragments to be exchanged between the ends of two chromosomes. Figure 4 illustrates these events, where each string represents a chromosome. Since evolutionary events affect long DNA regions (several thousand bases), the basic unit for comparison is not the nucleotide, but rather the gene. The computational study of rearrangement problems started after it was observed that several species share the same genes, however differently arranged. For example, most genes of the genome of _Brassica oleracea_ (cabbage) are identical in _Brassica campestris_ (turnip), but appear in a completely different order. When two whole genomes are compared, the goal is that of finding a sequence of evolutionary events that, applied to the first genome, turn it into the second. Usually, the objective asks to find the _most par  
Figure 3: An example of evolutionary tree. _simonious_ set of events, and the solution provides a lower bound on the \"amount of evolution\" between the two genomes. This bound can be interpreted as an evolutionary distance, and can be used to compute phylogenetic trees over a set of species. Species which are at short evolutionary distance should be placed very close in the tree (i.e., their paths to the root should intersect rather soon at a common ancestor). Depending on the type of evolutionary distance used, there may be many distinct evolutionary trees over the same set \(S\) of species. When many trees are available, it is important to compare them and to find what they have in common. This problem is called the _tree consensus_ or _tree reconciliation_. A similar problem can be posed also in the opposite direction. That is, given \"small\" trees over some subsets of \(S\), find a supertree, over all the species, which best agrees with the input trees. This problem is called _supertree reconstruction_. We can then define the last problem area:  
**Problem area # 5:** Evolution. _Comparison of whole genomes to highlight evolutionary macro events_ (_inversions, transpositions, translocations_). _Computation of evolutionary distances between genomes. Computation of common evolutionary subtrees or of evolutionary supertrees._  
Figure 4: Five types of evolutionary events