Subsections

## lkh

Computes an intuitively nice marker ordering using 2-points loglikelihoods.

#### Synopsis:

The lkh command is invoked as either one of :

• lkh Options
• lkh NbRun CollectMaps

#### Description:

The lkh command converts the current marker selection and associated genetic / Radiated Hybrid data into a Traveling Salesman Problem which is solved using Keld Helsgaun's LKH software. LKH is based on the Lin-Kernighan heuristic. It is possible to collect every tour found by LKH into the CarthaGene heap, in order to get a map with a possible better multipoint loglikelihood.

#### Arguments:

• Options : -u to obtain the synopsys of the normal use, -h to print a one line description, -H to print a short help.
• NbRun : Repeats NbRun times the LK heuristic. At each run, LKH tries different starting points (the number of starting points is equal to the number of markers ; if the heap was not empty, the best map in the heap is used as the first starting point, other starting points are randomly generated).
• CollectMaps : Possible values are -1, 0, 2, 3, 4 and 5. If CollectMaps >= 0 then every tour found by LKH is inserted into the CarthaGene heap. Moreover, a positive value sets the backtrack move type of LKH. If set to -1, only locally optimal tours w.r.t. the LK neighborhood are inserted into the heap.

nothing.

#### Example:

```CG> dsload Data/rh.cg
{1 haploid RH 53 118 /homes/thomas/carthagene/test/Data/rh.cg}
CG> lkh 1 -1
[-822.89]
Best map with log10-likelihood = -822.89
TSP: optimum= 801.055000 lowerbound= 801.035800 gap= 0.002397% totaltime= 0.07

Map -1 : log10-likelihood =  -822.89
-------:
Set : Marker List ...
1 : MS1 G39 MS3 MS2 G37 G40 G36 MS4 G3 G4 MS5 G1 G2 MS6 MS7 MS9 MS8 G21 G2\
6 G22 G25 G23 G27 G24 G28 G34 G33 G30 G31 G29 G32 G35 MS13 MS20 G10 G9 MS19 G\
19 MS17 G20 G11 G8 G7 G12 G13 G16 G6 G5 G17 G18 G14 G15 MS15

CG>
```