期刊
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
卷 5, 期 3, 页码 348-356出版社
IEEE COMPUTER SOC
DOI: 10.1109/TCBB.2008.16
关键词
computational biology; genome rearrangements; signed permutations; sorting by reversals; common intervals; perfect; sorting evolution
In comparative genomics, algorithms that sort permutations by reversals are often used to propose evolutionary scenarios of large-scale genomic mutations between species. One of the main problems of such methods is that they give one solution while the number of optimal solutions is huge, with no criteria to discriminate among them. Bergeron et al. started to give some structure to the set of optimal solutions, in order to be able to deliver more presentable results than only one solution or a complete list of all solutions. The structure is a way to group solutions into equivalence classes, and to identify in each class one particular representative. However, the design of an algorithm to compute this set of representatives without enumerating all solutions was stated to be an open problem. We propose, in this paper, an answer to this problem, that is, an algorithm which gives one representative for each class of solutions and counts the number of solutions in each class, with a better theoretical and practical complexity than the complete enumeration method. We give an example of how to reduce the number of equivalence classes obtained, using further constraints. Finally, we apply our algorithm to analyze the possible scenarios of rearrangements between mammalian sex chromosomes.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据