论文部分内容阅读
根据DNA测序片段数据的特点，提出了一个时间复杂度为0（nk2^2k2＋mlogm＋mk1）的单体型组装问题MEC／GI模型的参数化算法，其中m为片段数，n为单体型的SNP位点数，k1为一个片段覆盖的最大SNP位点数（通常小于10），k2为覆盖同一SNP位点的片段的最大数（通常不大于10）。对于实际DNA测序中的片段数据，即使m和n都相当大，该算法也可以在较短的时间得到MEC／GI模型的精确解，具有良好的可扩展性和较高的实用价值。