| Synopsis
| Synteny finds an approximation to the minimum
number of inversions needed to transform the input permutation
into a straight run (ascending or descending).
The input permutation is a list of the integers from 1 to n,
where n is the length of the list.
An inversion operation is a modification of a permutation
which selects a particular contiguous range and swaps its
order.
The problem of finding the synteny distance between to genomes
can be easily reduced to the problem of finding the number of
inversions to straighten the permutation.
The parameter k gives the function a hint on how much work
should be done, it is the number of partial solutions that
will be kept during the search.
The problem is NP-complete, so this algorithm searches for a
good approximate solution.
The higher k, the more work it will be done.
For a particular problem, the amount of work is linear in k.
By default k=10. |
| Examples
| > Synteny( [1,7,8,9,6,5,4,2,3] );
3
> Synteny( [4,5,6,1,2,3,7,8,9] );
3
|