2022年字符串数据处理方法借鉴 .pdf

字符串数据的处理主讲：戴永红 引例：“DNA 序列分类”问题 注：本题是2000 网易杯全国大学生数学建模竞赛A 题 2000 年 6 月，人类基因组计划中DNA全序列草图完成，预计 2001 年可以完成精确的全序列图，此后人类将拥有一本记录着自身生老病死及遗传进化的全部信息的“天书”。这本大自然写成的“天书”是由4 个字符 A，T，C，G 按一定顺序排成的长约30 亿的序列，其中没有“断句”也没有标点符号，除了这 4 个字符表示4 种碱基以外，人们对它包含的“内容”知之甚少，难以读懂。破译这部世界上最巨量信息的“天书”是二十一世纪最重要的任务之一。在这个目标中，研究 DNA全序列具有什么结构，由这 4 个字符排成的看似随机的序列中隐藏着什么规律，又是解读这部天书的基础，是生物信息学（Bioinformatics）最重要的课题之一。虽然人类对这部“天书”知之甚少，但也发现了DNA序列中的一些规律性和结构。例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4 个字符组成的64 种不同的3 字符串，其中大多数用于编码构成蛋白质的20 种氨基酸。又例如，在不用于编码蛋白质的序列片段中，A和 T的含量特别多些，于是以某些碱基特别丰富作为特征去研究DNA序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某些片段之间具有相关性，等等。这些发现让人们相信，DNA 序列中存在着局部的和全局性的结构，充分发掘序列的结构对理解 DNA全序列是十分有意义的。目前在这项研究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对象。这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。作为研究DNA序列的结构的尝试，提出以下对序列集合进行分类的问题：1）下面有20 个已知类别的人工制造的序列（见反面），其中序列标号110 为 A类，11-20 为 B类。请从中提取特征，构造分类方法，并用这些已知类别的序列，衡量你的方法是否足够好。然后用你认为满意的方法，对另外 20 个未标明类别的人工序列（标号 2140）进行分类，把结果用序号（按从小到大的顺序）标明它们的类别（无法分类的不写入）：A类 ；B类 。请详细描述你的方法，给出计算程序。如果你部分地使用了现成的分类方法，也要将方法名称准确注明。这 40 个序列也放在如下地址的网页上，用数据文件Art-model-data 标识，供下载：网易网址： 教育频道 在线试题；教育网： News mcm2000 教育网： 2）在同样网址的数据文件Nat-model-data 中给出了182 个自然 DNA序列，它们都较长。用你的分类方法对它们进行分类，像1）一样地给出分类结果。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 9 页 -附表 A-3：数据文件Art-model-data的内容(前 20 个)1.aggcacggaaaaacgggaataacggaggaggacttggcacggcattacacggaggacgaggtaaaggaggcttgtctacggccggaagtgaagggggatatgaccgcttgg 2.cggaggacaaacgggatggcggtattggaggtggcggactgttcggggaattattcggtttaaacgggacaaggaaggcggctggaacaaccggacggtggcagcaaagga 3.gggacggatacggattctggccacggacggaaaggaggacacggcggacatacacggcggcaacggacggaacggaggaaggagggcggcaatcggtacggaggcggcgga 4.atggataacggaaacaaaccagacaaacttcggtagaaatacagaagcttagatgcatatgttttttaaataaaatttgtattattatggtatcataaaaaaaggttgcga 5.cggctggcggacaacggactggcggattccaaaaacggaggaggcggacggaggctacaccaccgtttcggcggaaaggcggagggctggcaggaggctcattacggggag 6.atggaaaattttcggaaaggcggcaggcaggaggcaaaggcggaaaggaaggaaacggcggatatttcggaagtggatattaggagggcggaataaaggaacggcggcaca 7.atgggattattgaatggcggaggaagatccggaataaaatatggcggaaagaacttgttttcggaaatggaaaaaggactaggaatcggcggcaggaaggatatggaggcg 8.atggccgatcggcttaggctggaaggaacaaataggcggaattaaggaaggcgttctcgcttttcgacaaggaggcggaccataggaggcggattaggaacggttatgagg 9.atggcggaaaaaggaaatgtttggcatcggcgggctccggcaactggaggttcggccatggaggcgaaaatcgtgggcggcggcagcgctggccggagtttgaggagcgcg 10.tggccgcggaggggcccgtcgggcgcggatttctacaagggcttcctgttaaggaggtggcatccaggcgtcgcacgctcggcgcggcaggaggcacgcgggaaaaaacg 11.gttagatttaacgttttttatggaatttatggaattataaatttaaaaatttatattttttaggtaagtaatccaacgtttttattactttttaaaattaaatatttatt 12.gtttaattactttatcatttaatttaggttttaattttaaatttaatttaggtaagatgaatttggttttttttaaggtagttatttaattatcgttaaggaaagttaaa 13.gtattacaggcagaccttatttaggttattattattatttggattttttttttttttttttttaagttaaccgaattattttctttaaagacgttacttaatgtcaatgc 14.gttagtcttttttagattaaattattagattatgcagtttttttacataagaaaatttttttttcggagttcatattctaatctgtctttattaaatcttagagatatta 15.gtattatatttttttatttttattattttagaatataatttgaggtatgtgtttaaaaaaaatttttttttttttttttttttttttttttttaaaatttataaatttaa 16.gttatttttaaatttaattttaattttaaaatacaaaatttttactttctaaaattggtctctggatcgataatgtaaacttattgaatctatagaattacattattgat 17.gtatgtctatttcacggaagaatgcaccactatatgatttgaaattatctatggctaaaaaccctcagtaaaatcaatccctaaacccttaaaaaacggcggcctatccc 18.gttaattatttattccttacgggcaattaattatttattacggttttatttacaattttttttttttgtcctatagagaaattacttacaaaacgttattttacatactt 19.gttacattatttattattatccgttatcgataattttttacctcttttttcgctgagtttttattcttactttttttcttctttatataggatctcatttaatatcttaa 20.gtatttaactctctttactttttttttcactctctacattttcatcttctaaaactgtttgatttaaacttttgtttctttaaggattttttttacttatcctctgttat 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 9 页 -字符串数据的处理5.1 处理对象 此类数据以字符串形式出现，此类数据的一个典型代表是“DNA序列分类”问题中的数据。“DNA 序列分类”问题见附录A-4。5.2 处理目标 提取字符串中包含的信息：字符串中的字符种类、各个字符出现的频率、各种长度的子串出现的频率。5.3 处理步骤5.3.1 计算字符种类数和字符出现频率 确定字符串中字符的种类数，是字符串处理的前提。具体做法、找出字符串中的某一种字符，统计数量。、找出第二种字符，统计数量，并将之变换为第一种字符，此时第一种字符和原来的第二种字符只作为第一种字符看待，第二种字符待查。、重复步骤，直至字符串中所有字符变为一种字符。此时，即已得到字符串中字符的种类数和各个字符出现的次数，各个字符出现的次数除以所有字符出现的总次数即得各个字符出现的频率。5.3.2 计算 2-字符串的出现频率 2-字符串是由两个字符组成的子串。在知道字符串中字符的种类后，就可以知道所有可能的2-字符串的形式。若字符串中有种字符，则 2-字符串的可能形式有种。例如，字符串中有a、b、c三种字符，则 2-字符串的可能形式有 aa、ab、ac、ba、bb、bc、ca、cb和 cc 等 9 种。nnn 2-字符串的查找方式有3 种：“滚动”算法、“1-链接”算法和“2-链接”算法。例如，字符串 abccbca，按照“滚动”算法，依次有2-字符串 ab、bc、cc、cb、bc 和 ca 出现；按照“1-链接”算法（第一个和第二个字符组成一个2-字符串，第三个和第四个字符组成一个2-字符串，），依次有 2-字符串 ab、cc 和bc 出现；按照“2-链接”算法（第二个和第三个字符组成一个2-字符串，第四个和第五个字符组成一个2-字符串，），依次有 2-字符串 bc、cb 和 ca 出现。之所以有两种“链接”算法，是考虑到字符串可能是来自于更大字符串的片断，它的第一个字符可能是下一个2-字符串的开始字符，也可能是上一个2-字符串的结束字符。具体做法：、根据字符串中字符的种类，确定2-字符串的可能形式。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 9 页 -、利用“滚动”算法，计算出所有可能的2-字符串形式在字符串种出现的次数，每种形式出现的次数除以所有形式出现的总次数，即可得到每种形式出现的频率；同理，分别利用“1-链接”算法和“2-链接”算法，可以得到每种形式在相应算法下出现的频率。5.3.3 计算 3-字符串的出现频率 3-字符串是由三个字符组成的子串。在知道字符串中字符的种类后，就可以知道所有可能的3-字符串的形式。若字符串中有种字符，则 3-字符串的可能形式有种。例如，字符串中有a、b两种字符，则 3-字符串的可能形式有 aaa、baa、aba、bba、aab、bab、abb和 bbb 等 8 种。nnnn3-字符串的查找方式有4 种：“滚动”算法、“1-链接”算法、“2-链接”算法和“3-链接”算法。例如，字符串abccbca，按照“滚动”算法，依次有3-字符串 abc、bcc、ccb、cbc和 bca 出现；按照“1-链接”算法（第一个、第二个和第三个字符组成一个3-字符串，第四个、第五个和第六个字符组成一个3-字符串，），依次有 3-字符串 abc 和 cbc 出现；按照“2-链接”算法（第二个、第三个和第四个字符组成一个3-字符串，第五个、第六个和第七个字符组成一个 3-字符串，），依次有 3-字符串 bcc 和 bca 出现；按照“3-链接”算法（第三个、第四个和第五个字符组成一个3-字符串，第六个、第七个和第八个字符组成一个 3-字符串，），只有 3-字符串 ccb 出现 之所以有三种“链接”算法，是考虑到字符串可能是来自于更大字符串的片断，它的第一个字符可能是下一个3-字符串的开始字符，也可能是上一个3-字符串的中间字符，还可能是上一个3-字符串的结束字符。具体做法：、根据字符串中字符的种类，确定3-字符串的可能形式。、利用“滚动”算法，计算出所有可能的3-字符串形式在字符串种出现的次数，每种形式出现的次数除以所有形式出现的总次数，即可得到每种形式出现的频率；同理，分别利用“1-链接”算法、“2-链接”算法和“3-链接”算法，可以得到每种形式在相应算法下出现的频率。5.3.4 其他长度字符串的查找 类似 5.3.2 和 5.3.3，可以完成其他长度的字符串的查找。同理，除了“滚动”算法，4-字符串还有四种“链接”算法，5-字符串还有五种“链接”算法，。具体做法：与 5.3.2和 5.3.3的做法相似，只是更加繁琐。程序中只给出了计算任意长度字符串出现次数的算法，利用的是“滚动”算法。5.4 程序介绍 本部分程序有 6 个 Matlab 语言编写的 m文件组成。其中，data5input.m和data5main.m 文 件 属 于 m 脚本 文 件，data5onechar.m、data5twochar.m、data5threechar.m和 data5lookup.m 文件属于 m函数文件。data5input.m文件 本文件完成数据读入。文件将字符串数据存入元胞数组gene 中。data5onechar.m 文件 本文件计算字符串中字符的种类数和各个字符出现的频率。文件找出字符串中出现的字符种类，将它们存入元胞数组dstr 中，并以之名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 9 页 -作为函数返回值。data5twochar.m 文件 本文件完成 2-字符串的查找和出现频率的计算。文件第 4 行到第 11 行，找出所有可能的 2-字符串形式；第 14 行到第 22 行，利用“滚动”算法，计算各种2-字符串形式出现的次数；第25 行到第 36 行，利用“1-链接”算法，计算各种2-字符串形式出现的次数；第39 行到第 49 行，利用“2-链接”算法，计算各种2-字符串形式出现的次数；第52 行到第 71 行，计算并显示各种 2-字符串形式出现的频率。data5threechar.m文件 本文件完成 3-字符串的查找和出现频率的计算。文件第 4 行到第 15 行，找出所有可能的 3-字符串形式；第 18 行到第 28 行，利用“滚动”算法，计算各种3-字符串形式出现的次数；第31 行到第 42 行，利用“1-链接”算法，计算各种3-字符串形式出现的次数；第45 行到第 54 行，利用“2-链接”算法，计算各种3-字符串形式出现的次数；第57 行到第 67 行，利用“3-链接”算法，计算各种 3-字符串形式出现的次数；第 69 行到第 110 行，计算并显示各种 3-字符串形式出现的频率。data5lookup.m 文件 本文件利用“滚动”算法，完成各种长度子串的出现次数的计算。data5main.m 文件 本文件是主程序部分。文件第 3 行到第 5 行，清空命令窗口，清除所有变量，关闭所有图形窗口；第 8 行，调用 data5input.m文件，将数据读入程序；第11 行到第 55行，完成字符串的各种处理。5.5 程序使用举例 以“DNA序列分类”问题中的数据为例，使用的是Matlab6.1。第一步：将本部分程序的6 个 m 文件和所要处理的图像文件复制到Matlab默认工作路径下的work 文件夹中(work文件夹的默认路径是：/matlab6.1/work)。第二步：打开 data5input.m文件，将字符串数据存入元胞数组gene 中，如图 5-1 所示。第三步：在命令窗口键入data5main，并按回车键，命令窗口如图5-2 所示。第四步：键入所要处理的字符串代号（1 代表第一个字符串，2 代表第二个字符串，代表第个字符串，这里要求用户在第二步中要注意输入顺序），并按回车键，命令窗口如图5-3 所示。nn第五步：选择处理方式，键入代号（笔者键入2），并按回车键，命令窗口如图 5-4 所示。第六步：若要继续用其他方式处理，键入代号（笔者键入8），并按回车键，命令窗口如图5-5 所示，接着进入第七步；否则，键入0，并按回车键，接着进入第八步。第七步：键入所要查询的子串（笔者键入ttt），并按回车键，命令窗口如图5-6 所示。若要继续用其他方式处理，键入代号，并按回车键，接着返回第六步；否则，键入0，并按回车键，命令窗口如图5-7 所示，接着进入第八步。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 9 页 -第八步：若要继续处理其他字符串，键入代号，并按回车键；否则，键入0，并按回车键，命令窗口如图5-8 所示。图 5-1 图 5-2 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 9 页 -图 5-3 图 5-4名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 9 页 -图 5-5 图 5-6名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 9 页 -图 5-7 图 5-8名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 9 页 -