标题： 基于邻接图打包的启发式方法用于考虑基因间区的DCJ距离 显示英文标题

标题： Heuristics based on Adjacency Graph Packing for DCJ Distance Considering Intergenic Regions

摘要： 在本工作中，我们探讨了邻接图打包问题的启发式方法，该方法可应用于双切割和连接（DCJ）距离问题。 DCJ是一种重排操作，考虑它的距离问题是用于基因组比较的一种 established 方法。 我们的启发式方法将使用一种称为邻接图的结构，该结构被调整以包含关于基因间区域、基因组中基因的多个拷贝以及多个环形或线性染色体的信息。 对基因组的唯一要求是，必须能够通过DCJ操作将一个转化为另一个。 我们提出了一种贪心启发式方法和一种基于遗传算法的启发式方法。 我们在人工基因组上的实验测试表明，使用启发式方法能够找到优于简单随机策略的良好结果。 显示英文摘要

摘要： In this work, we explore heuristics for the Adjacency Graph Packing problem, which can be applied to the Double Cut and Join (DCJ) Distance Problem. The DCJ is a rearrangement operation and the distance problem considering it is a well established method for genome comparison. Our heuristics will use the structure called adjacency graph adapted to include information about intergenic regions, multiple copies of genes in the genomes, and multiple circular or linear chromosomes. The only required property from the genomes is that it must be possible to turn one into the other with DCJ operations. We propose one greedy heuristic and one heuristic based on Genetic Algorithms. Our experimental tests in artificial genomes show that the use of heuristics is capable of finding good results that are superior to a simpler random strategy.