-----Discrete Optimization for
TSP-like Genome Mapping Problems
作者： D. Mester,
D. Ronin, M. Frenkel, A. Korol et al
出版： Nova Science Publishers, Inc.
索书号： Q755/D611/2010/Y
核酸测序技术的发展极大促进了基因组学的发展，测序的快速性精确性使得全基因组测序成为可能。而测序得到的海量数据，需要一些处理及拼接，才能得到最终有意义的基因组数据。随着测序技术的进步，横亘在数据里的问题变成了制约基因组学发展的重大问题。旅行商问题（TSP）又称为推销员问题、货郎担问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。本书《基因组作图中旅行商问题的离散最优化》则关注的是基因组作图分析中，一系列可能序列次序导致的旅行商式问题离散最优化。
在本书《基因组作图中旅行商问题的离散最优化》中作者开创性的用旅行商问题来模拟出基因组序列排序、序列进化排序的数学模型及算法，其中包括标记位点或者基因在多位点遗传作图、多同义位点遗传作图以及物理图谱中的排序问题。由于数据的标记点高噪音、高数据量、特殊次序带来的特殊限制，对于这些问题无法使用常规的切割平面算法、EAX交叉遗传算法及著名的Lin-Kernighan算法来解决。本书则运用了引导型进化策略算法来解决了遗传作图中的旅行商离散型最优化的问题。这种算法能解决多达2,500个点的遗传学基因组学中的旅行商离散最优化问题。
本书的作者们在解决遗传作图基因组作图的旅行商问题时并没有依照经典的解决算法如切割平面算法、Lin-Kernighan算法等来解决，而是创造性提出了引导型计划策略算法，使得遗传作图基因组作图中的TSP问题得到了有效解决。本书作为解决遗传图和基因组作图中的旅行商问题的专业论文，在内容和编排上具有如下特点：
第一，本书的内容专业性极强，在生物领域遗传作图中的排序问题中使用旅行商问题数学模型，提出了最优算法；
第二，编排紧凑合理，在关键问题上均画出了图表，给出了比较详细的介绍和推理解释；
第三，在生物遗传作图、基因组作图中均举出了实例，便于读者对算法的理解。
总之，本书作为生物问题算法解决方案的专业书籍，对于专业人员而言具有比较强的启发性和参考性。同时对涉及专业的初学者也能提供有益的帮助。
本书目录
前言
第一章 简介
第二章 遗传作图、基因组作图旅行商问题的引导型进化策略算法解决方案
第三章 多位点遗传作图
第四章 多同义位点遗传作图：形成、模式及算法
第五章 基因组物理图谱绘制中的旅行商问题
第六章 结论
参考文献
索引
（武汉大学生命科学学院 研究生 刘靖）