文摘

在现代生物信息学中,找到一个有效的方式分配序列片段与生物功能是一个重要的问题。摘要提出了一种基于上下文无关文法的结构方法从原始DNA或蛋白质序列中提取。这种方法是完全不同的从这些统计方法。此外,这种方法相比,拓扑entropy-based方法复杂结果的一致性和差异。

1。介绍

DNA序列分析成为现代分子生物学的重要组成部分。DNA序列是由四个核苷酸腺嘌呤(略)、胞嘧啶(C)、鸟嘌呤(G)、胸腺嘧啶(T)在任何顺序。有四个不同的核苷酸,核苷酸为最多只能代码氨基酸,但核苷酸为最大可能代码氨基酸。乔治•伽莫夫是第一个假定每三基地可以转化为一个氨基酸,称为密码子。马歇尔Nirenberg和海因里希·j·Matthaei首先阐明遗传密码的本质。短DNA序列可以包含更少的遗传信息,而大量的基地可能包含更多的遗传信息,任何两个核苷酸和开关的地方可能会改变遗传信息的意义。

序列安排可以产生许多不同的结果,但只有几个密码子存在于活体。一些序列不包含任何信息被称为垃圾DNA。找到一个有效的方法来分析序列片段对应基因功能也是一个具有挑战性的问题。

在最近的报纸,方法大致分为两类,序列复杂性(1,2)和结构模式分析(3- - - - - -8]。Koslicki [1)提出了一个计算序列复杂性的方法。他重新定义拓扑熵函数,这样的复杂性值将不会更长时间序列收敛到零。与单独的序列分成几段,它可以确定部分外显子和内含子在哪里,和有意义或无意义的。郝et al。7)DNA序列的图形表示形式,根据这篇文章,我们可以找到一些罕见发生子序列。张r和c t·张(4)使用four-nucleotide-related函数绘制3 d曲线图表分析four-nucleotide发生概率的数量。Liou et al。9给了一个新想法在建模复杂性对音乐节奏;摘要文本信息转化为可计算的值,所以电脑能得分的音乐节奏。

在本文中,我们提出一种新的计算方法序列不同于其他传统的方法。它不仅统计值,而且结构信息。我们四个核苷酸替换为树状结构在9)和使用数学工具计算复杂性的序列值。我们可以比较两个序列值和确定这两个序列之间的不同。在生物医学部分,我们可以使用这种技术来寻找新病毒的有效药物和优先级。

2。DNA序列用树形结构表示

我们的方法使用Lindenmayer系统(10- - - - - -12从树状结构]属性之间的计算复杂性9];这是一个不同的方式计算序列的复杂性。首先,我们介绍一下DNA树和DNA序列转换为树状结构。DNA树是二叉树,每个子树也是一个DNA树。每个树节点是一个终端节点或节点有两个儿童(分支机构或后代)。

Lindenmayer系统是一个强大的重写系统用来模拟植物的生长过程的发展。我们将介绍部分2.2在细节。Lindenmayer系统使用一些初始和重写规则来构造美丽的图形。因为它可以从重写规则构造一个树,它还可以提取从树上重写规则。在本节中,我们将使用工具来生成树的规则。

我们使用固定树表示的核苷酸碱基A、T、C、G(见图1)。当我们这个方法适用于氨基酸序列,我们可以构建更多的氨基酸,树表示。

转移DNA序列树时,我们将取代每个词树元素一步一步,和两个连续的树可以把一个更大的树。前面的步骤后,将转移到一个DNA DNA序列树(参见图2)。

2.1。将字符串的DNA序列

我们的DNA树的计算复杂度,我们需要一些规则将树转换为另一种结构。我们使用一个堆栈同样DNA层次树结构来表示,称为括起来的字符串。DNA树可以转移到一个独特的将字符串由以下符号,它可以转移回到原来的树:(我) 树节点的当前位置;它可以取代任何单词或被省略;(2) 下面的字符串将表达正确的子树;(3) 下面的字符串将表达左子树;(iv) 这个符号是配对;”“一个子树表示,“”;显示所有的将字符串的子树;(v) 看到描述。

前面的符号后,人物3表明核苷酸基础和T代表树可以转让和,分别。

和图4将字符串的图吗2。我们可以看到,当树生长,字符串似乎更多的冗余。因为我们这里只关注DNA树,我们可以简化括起来的字符串表示。首先,我们的树只有两个子树。第二,““符号树是微不足道的。这两个特色,我们可以省略”“符号括起来的字符串并使用只有四个符号,,−),代表树木。在我们的情况下,““一个子树表示,““显示所有的将字符串的子树。表示下一个“−“符号树是当前节点的左子树,和“+”是一个右子树亦然。图5是将字符串的简单字符串如图4。

2.2。与L-System DNA序列来表示

当我们获得DNA树和括起来的字符串表示,我们需要重写规则分析树结构。有一些类型的重写机制如乔姆斯基语法和Lindenmayer系统(L-system短)。两个字符串重写机制最大的区别在于所使用的技术应用产品。乔姆斯基语法适用于顺序应用产品,而L-system是平行的。在我们的结构,应用L-system表示比乔姆斯基语法。

由生物学家介绍了L-system Lindenmayer 1968年(13]。的核心概念L-system重写。一般来说,重写技术用于定义先后更换零件复杂对象的一个简单的初始对象,使用一组重写规则或作品。在下一节中,我们将介绍如何使用L-system树我们的DNA。L-system定义如下。

定义1。L-system乔姆斯基语法语法非常相似,定义为一个元组(14]: 在哪里(我) 是一个字母,(2) (启动、公理或引发剂)的符号是一个字符串定义系统的初始状态,(3) 被定义为一个生产地图吗与为每一个在。单位生产假定。这些符号被称为常量或终端。

2.3。DNA序列的重写规则

正如前面所讨论的,我们想从DNA树生成规则。在本节中,我们将解释如何重写规则适用于那些树。我们可以应用不同的变量来每个节点。由于先前描述的技术总是生成的两个子树每个节点,每一个中间节点,他们总是可以解释在以下格式: 在哪里表示当前节点,表示它的左子树,分别表示它的右子树。我们举个例子如图6;离开树有三个节点,只非终结符根节点,它可以写成。有五个节点树,根在左子树和右子树。左子树是终端,但不是。有两个终端子树和,所以这棵树可以写成和。

2.4。将字符串的重写规则

同样,我们也可以使用重写规则生成括起来的字符串。DNA的重写规则树部分所示2.3,我们写与左、右子树树。注意,我们称之为和非终结符。在本节中,终端节点将脱离树木,我们使用“零”来表示一个终端。这些树将有一个相应的将字符串如下:。”“代表左子树,而””表示右子树。因此,我们可以代替的重写规则 ,“”是将字符串的每个子树的重写规则。为了可读性,我们替换单词如“”和“”。在图7,我们将展示将字符串的重写规则树的图3。

正如我们可以看到的,有“null”规则。那些“null”没有显著影响我们的算法,我们简单地忽略null。现在,图3可以应用新的重写规则而不琐碎的null如图8。

当树长大,重写规则可以生成相同的规则。假设我们有以下规则: 这些规则可以生成一个括起来的字符串,因此,一个DNA树。所有这些规则形成一个规则集,它代表了一个独特的DNA树。当我们看和,他们有相同的结构,因为他们都有一个右子树和没有左子树。唯一的区别是,一个的子树另一个是。我们将定义两个术语来表达两个重写规则之间的相似性,和这些术语可以简化复杂性分析。

2.5。同态和同构的重写规则

年底前一节中,我们讨论了和几乎是相同的。我们如何总结或者组织一个有效的功能?Liou et al。9)给两个定义分类类似的重写规则描述如下。

定义2。同态的重写规则。我们定义的重写规则和重写规则相互同态当且仅当它们有相同的结构。

在细节,重写规则和重写规则DNA的树木都在相应的位置或子树都没有。无视所有非终结符,如果规则和规则生成相同的将字符串,那么他们是同态的定义。

定义3。同构在水平在重写规则。重写规则和重写规则在同构深度如果他们是同态和非终结符相对深度的同构。同构在水平表明同态。

申请将字符串,我们忽略所有非终结符(4)如下:

我们发现,,,是同态的;他们生成相同的括起来的字符串,。但不是同态的其他规则;它将字符串。

让我们回忆起DNA树图示例2;我们将使用此图作为一个例子来阐明这些定义。现在我们一些节点如图9;有树的A, B, C, D,分别树,树B, C,树和树D树同构树深度0到3 C,但他们不是同构深度4。树乙同构树深度从0到2 C,但他们不是同构深度3。D不是同构其他树木,也不是同态其他树木。

在我们定义规则之间的相似性通过同态和同构,所有的规则划分为不同的子集,每个子集都有相同的相似关系。现在我们列出所有图的重写规则2成表1但忽视终端规则,如“零”和转移规则的名字类名(或类数)。例如,我们可以给终端类重写规则。”空”,一个规则链接两个终端;我们可以给他们””;在这里是终端类。进行分类后,我们不仅获得新的重写规则集,还一个上下文无关的语法,可以转换为自动机。

在表1、规则等,和在同构深度1和分配给类4。有二十个这样的规则分类之前,所以我们写”(20)”。等类似的规则,,同构在深度0,有47个这样的规则。他们都是分配给类1遵循类似的分类过程。中列出的所有规则的分类表2。注意,这部分还提出了一种新的方法来转换上下文敏感的上下文无关语法。

3所示。DNA序列的复杂性

当我们将DNA序列的重写规则和分类这些规则我们试图探索树中的冗余,将构建认知地图的基础(15]。我们计算的复杂性树代表这些分类规则。我们知道一套分类重写规则也是一个上下文无关的语法,所以有一些方法计算复杂度的重写规则如下。

定义4。上下文无关文法的拓扑熵。拓扑熵(上下文无关语法)CFG可以评估通过以下三个过程(16,17]。(1)为每一个变量与产品(Greibach形式), 在哪里是终端和非终结符。正式的每个变量的代数表达式 (2)通过替换每个终端与一个辅助变量,一个获得母函数 在哪里是长度的字数从天而降。(3)让是最大的一个,,尽管。前面的级数收敛的时候。的拓扑熵是收敛半径作为

我们的产品有一些区别上述定义。首先,我们的产品都写在Chomsky-reduced形式代替Greibach形式。第二,DNA序列是有限的;它产生有限的树,但是前面的公式应用于无限的序列。为了方便在DNA树的情况下,我们重新定义如下9]。

定义5。DNA拓扑熵的上下文无关语法树。(1)假设有类的规则,每个类包含规则。让,,,每个有以下形式: (2)的生成函数有一个新的形式如下: 如果没有任何非终结符变量,我们准备好了吗。(3)制定后生成函数,我们打算找到的最大价值,是收敛的。注意,我们使用表示DNA树的根节点的规则。在获得最大的价值,的,,我们设置的收敛半径。我们定义的复杂性DNA树

现在我们可以做一些例子的计算过程的复杂性。根据我们的定义,给定值参数表中列出的类3。有五类,所以我们得到的公式,先后。他们是

重新安排前面的方程,我们得到一个二次:

解决,我们获得的公式 在哪里

最后,收敛半径,和复杂性,从这个公式,可以得到。但是,计算直接是困难的,所以我们使用迭代和地区测试来近似的复杂性;细节如下。(1)重写生成函数 (2)的价值来。当对所有规则,我们说达到收敛,但是不是我们想要的。在这里,我们组为每个迭代。(3)现在我们可以测试是否收敛或发散是几号。我们使用二叉搜索测试每个实数之间和;在每个测试收敛,我们将更大下次,但当发散,我们组小下一个时间。运行更多的迭代将获得更精确的半径。

4所示。结果

2011年,Koslicki [1]给出了一个有效的方法来计算DNA序列的拓扑熵。他使用固定长度取决于subword大小来计算拓扑熵序列。例如,在图10(所有DNA和氨基酸数据可以在NCBI的网站,http://www.ncbi.nlm.nih.gov/),序列长度字符,和有三个subword大小,,分别为蓝、红、绿线。对于较大的subword大小,需要更大的片段计算复杂性。所需的片段大小呈指数级增长,而序列的长度是不依赖subword增长率的大小,所以这对我们来说不是一个好方法。

我们提出一个新方法称为结构复杂性在前面部分,并使用我们的方法有几个好处而不是Koslicki方法,描述如下。(1)我们的结果是完全不同的,还有那些获得的拓扑熵方法;看到颜色的行数据11 14。这些数据表明,我们的方法更敏感的某些安排元素序列。(2)两个不同的字符交换位置会改变自Koslicki方法只计算统计值没有结构信息。结果是图所示11下方图表;测试序列重复相同的subword好几次了。对于蓝线,所有的复杂性从拓扑熵值相等的区域内重复subwords。对于红线,复杂性值取决于subword的结构。的片段序列不同于对方,我们的方法将评估不同的值。(3)我们的方法也可以计算氨基酸序列。Koslicki方法取决于字母大小和subword大小,例如,在基本的长度子字符串计算;由于标准氨基酸类型,它需要一个最小长度来计算,但氨基酸字符串通常很短。有时,Koslicki方法不能有效地计算氨基酸序列。图12表明,氨基酸序列的复杂性也可以由我们的方法计算。

我们还做了实验的数据,包括固定片段大小和固定方法测试序列(见图13和14)。在这里,我们定义Koslicki方法;片段大小是不再依赖subword大小。相反,固定长度的片段像我们的方法。这种变化使我们能够比较容易的数据,而不是局限于指数增长的片段大小了。在图13,我们发现对于更大的片段,曲线的复杂性将成为顺利因为片段为每个数据点包含更多的信息。我们注意到这些数据是一种常见的局部峰值;的简单序列区域足够大,我们仍然包含相同的简单序列片段大小。

当我们比较用同样的方法显示在图14同样,我们发现情况更明显。因此,如果我们有很多复杂性值和不同的大小,我们有机会恢复部分的DNA。

4.1。应用程序病毒序列数据库和其他序列

现在我们可以将我们的技术应用到中国词序列。Togawa et al。18)给复杂的汉字,但他的研究是基于数量的中风,这是不同于我们的方法。这里我们使用繁体编码系统。由于汉字的数量大于,我们不能直接使用单词字母,所以我们需要一些转换。我们读了中国词分为四个十六进制的字母,这样我们可以将序列替换为树表示和计算复杂性。

当涉及到生物医学部分,我们可以创建病毒比较数据库。一旦新的病毒和朊病毒被发现,它将很容易在第一次,选择相应的药物根据复杂性相互交叉比较在数据库中。近年来,我们专注于最重要的病毒等大肠杆菌O157: H7 (E。杆菌o157),肠道病毒71 (EV71)、甲型流感病毒亚型H1N1 (H1N1)流感病毒亚型H5N1病毒(H5N1),严重急性呼吸系统综合症(SARS)。近年来,这些病毒产生重大影响和威胁人类世界。我们测试这些病毒和朊病毒表中列出4。在这里我们可以看到,所有由Koslicki朊病毒地区无法分析方法,但是我们可以做到。

最后,如果任何对象可以写成一个序列,并存在树表示的字母序列,我们可以计算对象的复杂性。

5。总结

在本文中,我们给出一个方法计算DNA序列的复杂性。传统的方法集中在统计数据或简单地探讨了结构复杂性没有价值。在我们的方法中,我们将DNA序列DNA树与树表示形式。

然后我们把树与上下文无关的语法格式,这样它就可以被分类。最后,我们使用重新定义生成函数,找到复杂度值。我们不仅给统计但也为DNA序列结构的复杂性,和这种技术可以用在许多重要的应用。

承认

这项工作是由美国国家科学委员会根据100年项目NSC - 2221 - e - 002 - 234 - my3。