Provide a Pareto frontier approximation.


The paretolkh command is invoked as either one of :


The paretolkh command creates a Pareto frontier from scratch. The result is a collection of maps, inserted into the heap, each map having a different number of breakpoints with a reference order. The current data set should be a merged by order between a biological data set and a reference order data set. paretolkh applies the weighted sum method for combining the 2-point loglikelihood (MLE) criterion from the biological data with the number of breakpoints (BP) criterion, approximated in the case of missing orthologous relationships. The weighted objective coefficient applied to the number of breakpoints is the product of a normalization factor and a weighted factor. The normalization factor $r$ is obtained by finding first the initial ranges of the two criteria ( $r = \frac{\max(MLE)-\min(MLE)}{\max(BP)-\min(BP)}$). The weighted factor is equal to $\frac{i}{Resolution - i}$ with $i$, a positive integer varying between $1$ and $Resolution - 1$. The Resolution parameter controls the number of iterations of the weighted sum method. Each iteration corresponds to a mono-objective Traveling Salesman Problem with a different coefficient value ( $\frac{r \times i}{Resolution - i}$) solved by Keld Helsgaun's LKH software. Each iteration uses as a first starting point the best map found by the previous iteration. In order to improve the Pareto frontier, CARTHAGENE first generates an initial map by optimizing only one single objective (2-point loglikelihood criterion first), and then to start from this map a sequence of LKH iterations by varying $i$ from $1$ to $Resolution - 1$. This search strategy is applied twice. The second time, it starts from the best map found with the minimum number of breakpoints and vary $i$ from $Resolution - 1$ to $1$. The final map found by each iteration is called supported and is locally optimal w.r.t. the LKH neighborhood. Some maps in the Pareto frontier are called dominated if there exists another map in the frontier which has less breakpoints and a better likelihood. The best map in the frontier is called balanced. The NbRun and CollectMaps parameters control the LKH method. See lkh 2.5.8. In order to get non supported maps and a better Pareto frontier approximation, use CollectMaps greater than or equal to 0. Each map found by the weighted sum method is assessed by computing the exact multipoint likelihood2.8 and the exact number of breakpoints. Note that the loglikelihoods written during the iterative process have no meaning (internal use only).

Try paretolkh 10 1 0 as default parameter values.




See also:

Thomas Schiex 2009-10-27