检索结果-内蒙古大学图书馆

sorting permutations by reversals through a Hybrid Genetic Algorithm based on Breakpoint Elimination and Exact Solutions for Signed permutations

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2013年 292卷 119-133页

作者： Soncco-Alvarez, Jose Luis Ayala-Rincon, Mauricio Univ Brasilia Dept Matemat & Ciencia Comput Grp Teoria Computac Brasilia DF Brazil

sorting permutations by reversals is one of the most challenging problems related with the analysis of the evolutionary distance between organisms. Genome rearrangement can be done through several operations with biological significance, such as block interchange, transposition and reversal, among others;but sorting by reversals, that consists in finding the shortest sequence of reversals to transform one genome into another, came arise as one of the most challenging problems from the combinatorial and algebraic points of view. In fact, sorting by reversal unsigned permutations is an NP-hard problem, for which the question of NP-completeness remains open for more than two decades and for which several interesting combinatorial questions, such as the average number of reversals needed to sort permutations of the same size, remain without solution. In contrast to the unsigned case, sorting by reversals signed permutations belongs to P. In this paper, a standard genetic algorithm for solving the problem of sorting by reversals unsigned permutations is proposed. This approach is based on Auyeung and Abraham's method which uses exact solutions for the signed case in order to build approximate solutions for the unsorted one. Additionally, an improved genetic algorithm is proposed, that in the initial generations applies reversals that simultaneously eliminate two breakpoints, a heuristic mechanism used by several approximation algorithms. As control mechanism for estimating the precision of the results, a correct implementation of an 1.5-approximation algorithm was developed. Also, the results were compared with permutations for which exact solutions are known, such as Gollan's permutations and their inverses. Several experiments with randomly generated permutations were performed and the results showed that in average the precision of the outputs provided by both the standard and improved genetic algorithms overcome the results given by the 1.5-approximation algorithm as

关键词： sorting permutations by reversals Genetic Algorithms Approximate Algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：