## 3 The papers
### Problem area # 2 : hybridization and microarrays  
Physical mapping._Physical mapping_ by hybridization is the problem of reconstructing the linear ordering of a set of genetic markers, called _probes_, along a target (such as a BAC, Bacterial Artificial Chromosome). The input of this problem usually consists of a probe/clone 0-1 incidence matrix, i.e., a matrix specifying, for each pair (probe, clone), if the probe is contained in the clone. * [21]: [PERSON], [PERSON] and [PERSON] and [PERSON] (1995) [RED]  
show how to cast this problem into a special type of TSP, the _Hamming distance_ TSP, which is then solved by the use of standard TSP heuristics. A very similar problem concerns the construction of _Radiation Hybrid_ (RH) maps. Radiation hybrids are obtained by (i) breaking, by radiation, a human chromosome into several random fragments (the markers) and (ii) fusing the radiated cells with rodent normal cells. The resulting hybrid cells, may retain one, none or many of the fragments from step (i). For each marker \(j\) and each radiation hybrid \(i\), an experiment can tell if \(j\) was retained by \(i\) or not. As before, the problem consists in ordering the markers, given \(M\). The problem is studied in
* [22]: [PERSON] and [PERSON] (1997) [RED]
* [23]: [PERSON]. [PERSON] and [PERSON] and [PERSON] (2000) [RED]  
Two different measures are widely used to evaluate the quality of a solution. The first is a combinatorial measure, called Obligate Chromosome Breaks (OCB), while the second is a statistically based, parametric method of maximum likelihood estimation (MLE). The optimization of both measures can be reduced to the solution of a suitable TSP. In their work, [PERSON] at al. used _Simulated Annealing_, with the 2-OPT neighborhood structure of Lin and Kernighan [24], for the solution of the TSP. The software package RHO (Radiation Hybrid Optimization), developed by [PERSON] et al., was used to compute RH maps for the 23 human chromosomes. For 18 out of 23 chromosomes, the maps computed with RHO coincided with the corresponding maps computed at the Whitehead Institute, by experimental, biological, techniques. The remaining maps computed by using RHO were superior to the Whitehead maps with respect to both optimization criteria. * [25]: [PERSON], [PERSON], [PERSON], [PERSON], [PERSON] (2000) [RED]  
describe an improvement of the RHO program, obtained by replacing the simulated annealing module for the TSP with the state-of-the-art TSP software package, CONCORDE [26]. Computational experiments showed that the maps computed by the program over hybrid data from the panels Genebridge 4 and Stanford G3, were more accurate than the previously known maps over the same data. The physical mapping problem has been attacked also by integer programming formulations, solved via Branch-and-Cut. * [27]: [PERSON], [PERSON], [PERSON], [PERSON] and [PERSON] (1997) [ILP]
* [28]: [PERSON]. [PERSON] and [PERSON] (1999) [ILP]  
The second of these works, in particular, focuses on _physical mapping with end-probes_, in which the probes used for hybridization come in pairs. Each pair consists of two short sequences flanking the ends of some longer clone. Microarrays and feature selection.Hybridization is at the basis of microarrays technology. A microarray is a matrix in which each cell is labeled with some probe. Microarray experiments (heavily parallel as the number of cells in a microarray is typically quite large), can tell which subset of the probes hybridize to the sample. The characteristic vector of the subset can then be used as _a signature_ for the sample, as long as no other sample has the same characteristic vector. The problem of selecting probes which yield \"good\" signatures for a set of samples is solved by integer programming in
* [29]: [PERSON], [PERSON], [PERSON], [PERSON] and [PERSON] (2004) [ILP]  
The above problem belongs to the general class of _feature selection_ problems. The incidence of a probe to a target can be seen as a feature that the target may or may not possess.