基于加权有向多重图的DNA序列比较的非比对方法研究

Alignment-free methods play an important role in response to the overwhelming burst in data generated by molecular biology initiatives. It is the focus of Post Genome Era. This project establishes a new method of graphical representation, in which DNA sequences are converted into networks. By mapping to weighted directed graph, distances between adjacent k-word in DNA sequence are converted into paths in the network. Existing knowledge and algorithms from graph theory will both promote development of data mining in DNA sequences and provide a new strategy in sequence comparison. The diameter, degree sequence, various paths of properties, scales and numbers of clusters in this new network, together with special features of DNA network, average distance among the same k-words, regression distance, constitute a feature vector. Sequences comparison can be done based on this feature vector. Based on information in paths among k-word, the positional information of k-word is explored. Based on modules' properties in the network, the relationship information of k-word is explored. Mathematical descriptors are created for describing invariants under the process of evolution(mutation, insertion, deletion, replication, shift). Through classification algorithms from SVM and Random Forest, features of network are selected. Based on the features, efficient alignment-free methods are proposed. This study includes establishment of several new efficient alignment-free methods and software tools for DNA sequences comparison. Furthermore, based on DNA sequences’ reconstructible properties from all their k-word counts, this project will also create the mathematical descriptors for data sets, in which the alignment-free methods are tested.

生物序列比较的非比对方法在处理日益增长的生物序列中发挥着重要作用，是后基因组时代的研究热点。本项目将DNA序列映射到加权有向图中，将k-词间的距离对应为网络中的路径长度，利用图论理论和算法为DNA序列的信息挖掘提供全新的策略。将网络的直径，度序列，各种特性的路径，团的大小及数量，及DNA序列网络的特殊具有的相同k-词间的平均距离，回归距离的特征，组成特征向量，利用该向量进行DNA序列比较。计算有向图中的路径信息，挖掘k-词的位置信息；分析有向图中的模块化特性，挖掘k-词间的关联信息。构造DNA序列在进化过程中（如突变、插入、删除、复制、转移等）的相对不变量。通过SVM分类算法和随机森林方法进行特征选择，建立精准高效的序列非比对方法。本项目的研究将建立若干准确高效的非比对方法，为DNA序列的比较提供工具支持，并将给出非比对方法数据测试集的k-词组成唯一生成的数学指标，推动非比对方法研究。

生物序列比较的非比对方法在处理日益增长的生物序列中发挥着重要作用，是后基因组时代的研究热点。基于k-词组成的生物序列非比对方法是其中的一类重要方法。基于k-词组成的非比对方法是经过实践检验的有效的生物序列比较方法。通过它们，我们对生物序列在多种角度和不同层面上有了丰富的了解。然而，基于k-词组成的生物序列非比对方法存在一些需要完善的问题。例如，k-词长度的选择依赖于生物序列数据，没有公认的选择机制。. 本项目将DNA序列首尾相连生成环状结构。通过一一映射，将这个环状结构映射到有向网络中。在给定的有向图网络上，我们实现了查找所有欧拉回路的算法。一方面，基于这个算法，对于给定的DNA序列，该算法能确定k-词组成唯一生成该序列的k值，为我们从理论层面剖析DNA序列提供了切入点。另一方面，我们提出了4种非比对的序列比较方法，对每一种方法中距离的k词长度，给出了有理论依据的选择机制；对于每一种方法，我们分别选取了3个真实生物序列集，基于我们提出的距离，进行进化树重建得到的结果与普遍接受的权威结果高度一致；这些高效的非比对方法，为DNA序列的比较提供工具支持。以上两个方面都有助于推动DNA序列的非比对方法研究。. 另外，我们在与DNA序列非比对方法中的图形表示方法密切相关的图的交叉数领域得到了几个结果。证明了完全4部图K_{1,1,1,3}与路径P_n笛卡尔乘积图的交叉数为10n；给出了完全4部图K_{1,1,m,n}的交叉数的下界；证明了10个六阶图与路径P_n笛卡尔乘积图的交叉数；令G_m是在完全二部图K_{1,m}中添加3条边得到的简单图，并且添加的3条边有一个公共的端点。对于任意的自然数m和n，我们证明了G_m与P_n笛卡尔乘积图的交叉数。