IEEE/ACM Trans Comput Biol Bioinform. 2018 Mar-Apr;15(2):352-363. doi: 10.1109/TCBB.2015.2474400. Epub 2015 Aug 28.
Genome Rearrangements are large-scale mutational events that affect genomes during the evolutionary process. Therefore, these mutations differ from punctual mutations. They can move genes from one place to the other, change the orientation of some genes, or even change the number of chromosomes. In this work, we deal with inversion events which occur when a segment of DNA sequence in the genome is reversed. In our model, each inversion costs the number of elements in the reversed segment. We present a new algorithm for this problem based on the metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP) that has been routinely used to find solutions for combinatorial optimization problems. In essence, we implemented an iterative process in which each iteration receives a feasible solution whose neighborhood is investigated. Our analysis shows that we outperform any other approach by significant margin. We also use our algorithm to build phylogenetic trees for a subset of species in the Yersinia genus and we compared our trees to other results in the literature.
基因组重排是影响进化过程中基因组的大规模突变事件。因此，这些突变与点状突变不同。它们可以将基因从一个位置移动到另一个位置，改变一些基因的方向，甚至改变染色体的数量。在这项工作中，我们处理当基因组中的 DNA 序列片段反转时发生的倒位事件。在我们的模型中，每个倒位都要花费反转片段中的元素数量。我们提出了一种新的基于元启发式算法的算法，称为贪婪随机自适应搜索过程（GRASP），该算法通常用于寻找组合优化问题的解决方案。本质上，我们实现了一个迭代过程，其中每个迭代接收一个可行解，然后调查其邻域。我们的分析表明，我们的表现明显优于其他任何方法。我们还使用我们的算法为耶尔森氏菌属的一个物种子集构建系统发育树，并将我们的树与文献中的其他结果进行比较。
