Braga Marília D V, Gautier Christian, Sagot Marie-France
Université de Lyon, F-69000, Lyon, France.
Algorithms Mol Biol. 2009 Dec 30;4:16. doi: 10.1186/1748-7188-4-16.
The reversal distance and optimal sequences of reversals to transform a genome into another are useful tools to analyse evolutionary scenarios. However, the number of sequences is huge and some additional criteria should be used to obtain a more accurate analysis. One strategy is searching for sequences that respect constraints, such as the common intervals (clusters of co-localised genes). Another approach is to explore the whole space of sorting sequences, eventually grouping them into classes of equivalence. Recently both strategies started to be put together, to restrain the space to the sequences that respect constraints. In particular an algorithm has been proposed to list classes whose sorting sequences do not break the common intervals detected between the two initial genomes A and B. This approach may reduce the space of sequences and is symmetric (the result of the analysis sorting A into B can be obtained from the analysis sorting B into A).
We propose an alternative approach to restrain the space of sorting sequences, using progressive instead of initial detection of common intervals (the list of common intervals is updated after applying each reversal). This may reduce the space of sequences even more, but is shown to be asymmetric.
We suggest that our method may be more realistic when the relation ancestor-descendant between the analysed genomes is clear and we apply it to do a better characterisation of the evolutionary scenario of the bacterium Rickettsia felis with respect to one of its ancestors.
将一个基因组转化为另一个基因组的反转距离和最优反转序列是分析进化情景的有用工具。然而，序列数量巨大，需要使用一些额外标准来获得更准确的分析。一种策略是寻找符合约束条件的序列，比如共同区间（共定位基因簇）。另一种方法是探索排序序列的整个空间，最终将它们分组为等价类。最近，这两种策略开始结合起来，将空间限制在符合约束条件的序列上。特别是，已经提出了一种算法来列出其排序序列不会破坏在两个初始基因组A和B之间检测到的共同区间的类。这种方法可能会减少序列空间，并且是对称的（将A排序为B的分析结果可以从将B排序为A的分析中获得）。
我们提出了一种替代方法来限制排序序列的空间，使用逐步而非初始检测共同区间（在应用每次反转后更新共同区间列表）。这可能会进一步减少序列空间，但结果表明该方法是不对称的。
我们认为，当所分析基因组之间的祖先-后代关系明确时，我们的方法可能更符合实际情况，我们将其应用于更好地描述猫立克次氏体相对于其一个祖先的进化情景。
