Aug. 7, 2012, midnight by Rosalind Team
Topics: Combinatorics, Genome Rearrangements
Synteny Blocks Have Orientations
In “Enumerating Gene Orders”, we introduced synteny blocks for two different species, which are very similar areas of two species genomes that have been flipped and moved around by rearrangements. In that problem, we used the permutation to model the order of synteny blocks on a single chromosome.
However, each strand of a DNA molecule has an orientation (as RNA transcription only occurs in one direction), and so to more prudently model chromosomes using synteny blocks, we should provide each block with an orientation to indicate the strand on which it is located. Adding orientations to synteny blocks requires us to expand our notion of permutation so that each index in the permutation has its own orientation.
A signed permutation of length
Given: A positive integer
Return: The total number of signed permutations of length
8 -1 -2 -1 2 1 -2 1 2 -2 -1 -2 1 2 -1 2 1