大规模生物数据计算的优化建模与高效算法研究

With the implementation of the Human Genome Project and the development of modern genome sequencing technologies, it is imperative to compute large-scale biological data efficiently. There are two unavoidable problems in biological data computing -- the large-scale biological data clustering and the multiple longest common subsequence searching of large-scale biological sequences. These two important problems can provide new methods and technologies for sequence fragment detection, splicing, gene expression analysis, RNA and protein structure function prediction, biological co-evolution origin exploration, disease surveillance, new drug development, and so on. However, the currently available models for the multiple longest common subsequence problem of the biological sequences are too complex, and the time complexity and space complexity of the existing algorithms are extremely large. Hence, they cannot be applicable to the multiple longest common subsequence problem of the large-scale biological sequences, even cannot be applicable to the problems with more than 1000 sequences. Meanwhile, when the existing clustering models and algorithms are applied on biological data, they usually only consider global information without considering local (fragment) information. However, some local (fragment) information may be really important, thus leading to a large error of clustering models and an inaccurate result of clustering algorithms. Therefore, it is necessary to study new models and efficient algorithms of these two important problems. This project studies new optimization models and efficient algorithms of the large-scale biological data clustering and the multiple longest common subsequence of the large-scale biological sequences. We aim to overcome the shortcomings of currently available models and algorithms, putting forward some simple, reasonable and easy execution models and fast algorithms.

随着人类基因组计划的实施以及现代基因组测序技术的发展，需要对大规模生物数据进行计算。而大规模生物数据的聚类和大规模生物序列最长公共子序列的寻找是生物数据计算的两个重要问题。可为序列片段测定、拼接、基因表达分析、RNA和蛋白质结构功能预测、生物共同进化起源的探索、疾病监测、新药研制等提供新的方法和技术。但目前生物序列最长公共子序列的模型复杂，算法时空消耗太大，难以适用于大规模问题(对1000个以上序列的问题都无法解决)；目前的聚类模型和算法在用于生物数据时往往只考虑全局信息，没有考虑生物数据的局部(片段)信息，有些片段信息却十分重要，导致聚类模型偏差大，聚类算法结果不准确。因此，研究这两个重要问题的新模型和高效算法十分必要。本项目针对大规模生物数据的聚类和最长公共子序列问题研究新的优化建模方法和相关模型的高效算法，克服已有模型和算法的缺陷，提出一些简单合理并易于计算的模型和快速高效的算法。

随着人类基因组计划的实施以及现代基因组测序技术的发展，需要对大规模生物数据进行计算。而大规模生物数据的聚类和大规模生物序列最长公共子序列的寻找是生物数据计算的两个重要问题。可为序列片段测定、拼接、基因表达分析、RNA和蛋白质结构功能预测、生物共同进化起源的探索、疾病监测、新药研制等提供新的方法和技术。但目前生物序列最长公共子序列的模型复杂，算法时空消耗太大，难以适用于大规模问题(对1000个以上序列的问题都无法解决)；目前的聚类模型和算法在用于生物数据时往往只考虑全局信息，没有考虑生物数据的局部(片段)信息，有些片段信息却十分重要，导致聚类算法结果不准确,泛化能力弱。因此，研究这两个重要问题的新模型和高效算法十分必要。本项目针对大规模生物数据的聚类和最长公共子序列问题，研究新的优化建模方法和相关模型的高效算法，克服已有模型和算法的缺陷，提出了一些可处理大规模公共公共子序列的模型，构造了一些可自动确定类数和类中心的聚类算法，并针对最长公共子序列模型和聚类模型涉及的大规模优化和多目标优化问题，提出了一些快速高效的算法。