Perfect Sorting by Reversals
In computational biology, gene order data is often modelled as signed permutations. A classical probleM in genome comparison is to detect conserved segments in a permutation, that is, genes that are colocalised in several species, indicating that they remained grouped during evolution. A second largely studied problem related to gene order data is to compute a minimum scenario of reversals that transforms a signed permutation into another. Several studies began to mix the two problems, and it was observed that their results are not always compatible: often parsimonious scenarios of reversals break conserved segments. In a recent study, Berard, Bergeron and Chauve stated as an open question whether it was possible to design a polynomial time algorithm to decide if there exists a minimuM scenario of reversals that transforms a genome into another while keeping the clusters of co-localised genes together. In this paper, we give this polynomial algorithm, and thus generalise the theoretical result of the aforementioned paper.
Marie-Prance Sagot Eric Tannier
INRIA Rhone-Alpes, Universite de Lyon 1, Prance
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
42-51
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）