在生命科学中,许多问题都可以抽象为计算机科学与数学中关于序列、树和串的组合问题。本文主要研究两个重要的生物信息学问题：寻找motif问题和RNA折叠问题。这两种问题简言之都是在许多生物学序列中寻找共同部分。　　近年来,生命科学的飞速发展带给我们越来越多的研究数据,如何在这些浩如烟海的数据中挖掘有用的信息已经成为当前科学家们需要面对的首要问题,并由此产生了研究生命的新学科：生物信息学,它以生物学实验室研究的数据为材料,利用网络和计算机技术,来实现对生命本质的研究、探索。　　本文考虑的第一个问题是寻找motif问题。在生物学中,基因的活性往往取决于一些称为motif的小片段的性质,寻找motif问题就是要在DNA序列中找出这些小的片段,然而,motif往往并不以本来面貌出现,合理的模型是允许未知的片段以少许错配、插入和缺失的形式出现在所研究序列中。我们可以描述寻找motif问题如下：给定一个序列集,以及一个未知片段,这个片段以少量变化的形式(诸如错配、插入和缺失)在不同位置出现每个序列中(序列中对应的片段即叫做motif),我们能否找出这些motif呢？在DNA序列中寻找motif是计算生物学中的一个基本问题,在基因调节中有十分重要的应用,基因序列数量的巨大让问题计算起来相当困难,而且其中的许多问题都是NP-hard的。近十年来,人们为此设计了许多启发式算法,但问题还远远没有解决。　　本文主要考虑motif变异的两个形式：嵌入和缺失。即允许未知片段以少许嵌入或缺失的形式出现在所研究序列中。我们刻画问题如下：问题3.1.1(d嵌入motif问题)给定∑域中的序列组　　S={s1,…,sn},|si|=m.i=1,…,n,以及整数d.L求一个长为L的字符串s,使s以至多嵌入d个字符的形式表现在每个si中,即存在si的长为L+d子串ti,满足s为ti的子序列。问题3.2.1(d段嵌入motif问题)给定∑域中的序列组　　S={s1,…,sn},|si|=m,i=1,…,n.