Platt D M, Dix T I
Department of Computer Science, Monash University, Clayton, 3168, Australia.
Genomics. 1997 Mar 15;40(3):490-2. doi: 10.1006/geno.1996.4588.
In this paper, a number of existing and novel techniques are considered for ordering cloned extracts from the genome of an organism based on fingerprinting data. A metric is defined for comparing the quality of the clone order for each technique. Simulated annealing is used in combination with several different objective functions. Empirical results with many simulated data sets for which the correct solution is known indicate that a simple greedy algorithm with some subsequent stochastic shuffling provides the best solution. Other techniques that attempt to weight comparisons between nonadjacent clones bias the ordering and give worse results. We show that this finding is not surprising since without detailed attempts to reconcile the data into a detailed map, only approximate maps can be obtained. Making N2 pieces of data from measurements of N clones cannot improve the situation.
本文考虑了许多现有和新颖的技术，用于根据指纹数据对来自生物体基因组的克隆提取物进行排序。为比较每种技术的克隆排序质量定义了一个度量。模拟退火与几种不同的目标函数结合使用。对于许多已知正确解的模拟数据集的实证结果表明，一种简单的贪心算法加上一些后续的随机洗牌能提供最佳解。其他试图对非相邻克隆之间的比较进行加权的技术会使排序产生偏差并给出更差的结果。我们表明这一发现并不奇怪，因为如果没有详细地尝试将数据整理成详细的图谱，就只能获得近似图谱。从N个克隆的测量中获取N²个数据并不能改善这种情况。
