自相似序列的复杂度理论及应用中的若干问题

In this project, we concentrate on the analysis of complexities of the self-similar sequences and its applications in the field of complex networks and bioinformatics, this is one of important issues regarding self-similar sequences and fractal geometry theory, and also the research hotspot of peers at home and abroad. 1) we shall give a systematic study on the additive and Lattice complexities of automatic sequences over the alphabet with more than three letters. 2) we shall investigate the fractal dimensions of functions generated by the k-Abelian complexities of a class of morphic sequences, as a consequence, we could build the inherent relationship among the fractal dimensions, the constant k and morphic sequences. 3) we shall develop the quantitative relationship between the indexes of morphic sequences and the indexes of corresponding Rauzy directed networks. 4) we shall show that how to characterize the slices of DNA genes with the abelian complexity by the method of empirical analysis, and then classify and predict the slices of DNA genes using the abelian complexity. These problems are relatively dependent but closely related, and of great theoretical and application significance.

本项目的研究内容主要涉及自相似序列的复杂度分析及复杂度理论在复杂网络和生物信息中的应用，是一个自相似序列和分形几何理论及应用中的重要研究课题，也是国内外同行所关注的研究热点。1）我们将系统深入地研究多字母自动机序列的加法复杂度和Lattice复杂度。2）研究由自相似序列的无界k-Abelian复杂度生成的分形函数图像的分形维数，进而寻求该维数与常数k及序列本身的依赖关系。3）发展一类代换序列与其Rauzy有向网络之间的内在联系。4）实证分析Abelian复杂度对DNA基因片段特征的刻画程度，进而以Abelian复杂度作为特征对DNA基因片段分类与预测。这些问题相对独立但密切相关，具理论及应用双重重要意义。

本项目的研究内容主要涉及自相似序列的复杂度分析及复杂度理论在复杂网络和生物信息中的应用，是一个自相似序列和分形几何理论及应用中的重要研究课题，也是国内外同行所关注的研究热点。1)关于自相似序列复杂度的正则性方面，证明出一个三字母类Thue-Morse序列的加法复杂度是2-正则的，说明了广义Thue-Morse序列的阿贝尔复杂度是周期的；同时还证明出对任意的k, Cantor序列的k-阿贝尔复杂度都是3-正则；（2）关于序列生成分形函数方面，我们构造出一类拟线性函数，其中包含一部分正则序列，得到其生成的分形函数图像的盒子维数的最优估计。 3)关于复杂网络与分形几何的交叉方面，对Sierpinski垫片的骨架网络的偏心距离和给出渐进估计。4)实证分析Abelian复杂度对DNA基因片段特征的刻画方面，我们将Abelian复杂度作为特征的一部分来对DNA基因功能片段特别是增强子进行分类与预测，改进了目前已有方法的准确率。这些问题相对独立但密切相关， 具理论及应用双重重要意义。