| Calling Sequence
| SignedSynteny(perm)
|
| Parameters
| | Name | Type | Description |
|
| perm
| list(integer) | a permutation |
|
| Return Type
| integer |
| Synopsis
| SignedSynteny finds the minimum
number of reversals needed to transform the input permutation
into an ascending straight run of positive integers.
The input permutation is a list of length n of the integers from 1 to n,
where each number is also assigned a sign plus or minus (plus is implicit).
A reversal operation modifies a signed permutation by swapping the order of
a particular contiguous range and flipping the sign of the elements in the
range. The problem of finding the synteny distance between two genomes,
with known direction of every gene in the genomes, can be reduced to the
problem of finding the number of reversals.
SignedSynteny runs in O(n) and is an implementation of the algorithm
described in "Kaplan et al., Faster and simpler algorithm for sorting signed
permutations by reversals, SODA '97, ISBN:0-89871-390-0, 344-351, 1997.",
except for a sub-algorithm to find connected components in a special graph.
A faster algorithm to find the connected components is given in
"Bader et al., A linear-time algorithm for computing inversion distance
between signed permutations with an experimental study, WADS '01,
ISBN:3-540-42423-7, 365-376, 2001." |
| Examples
| > SignedSynteny([8, 9, -6, -1, 3, 5, -7, 2, 4]);
8
> SignedSynteny([4, 5, 6, -3, -1, -2]);
4
|
| See also
| DrawTree, GapTree, LeastSquaresTree, PhylogeneticTree, Synteny |