📄 第三章.htm
字号:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>—</span><span
style='font-size:10.0pt'> </span><span style='font-size:10.0pt;font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>单独的字符；</span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;
text-indent:21.25pt;line-height:150%'><span style='font-size:10.0pt;font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>④</span><span
lang=EN-US style='font-size:10.0pt'> s</span><span style='font-size:10.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>、</span><span lang=EN-US style='font-size:10.0pt'>t</span><span
style='font-size:10.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>、</span><span lang=EN-US
style='font-size:10.0pt'>u</span><span style='font-size:10.0pt;font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>、</span><span
lang=EN-US style='font-size:10.0pt'>v</span><span style='font-size:10.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>、</span><span lang=EN-US style='font-size:10.0pt'>x </span><span
style='font-size:10.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>—</span><span lang=EN-US
style='font-size:10.0pt'> A*</span><span style='font-size:10.0pt;font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>中的序列；</span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;
text-indent:21.25pt;line-height:150%'><span style='font-size:10.0pt;font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>⑤</span><span
lang=EN-US style='font-size:10.0pt'> |s| </span><span style='font-size:10.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>—</span><span style='font-size:10.0pt'> </span><span
style='font-size:10.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>序列</span><span lang=EN-US
style='font-size:10.0pt'>s</span><span style='font-size:10.0pt;font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>的长度。</span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>为了说明序列<span lang=EN-US>s的子序列和s中单个字符，我们在s中各字符之间用数字标明分割边界。例如，设s=ACCACGTA，则s可表示为</span></span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>
0A1C2C3A4C5G6T7A8 。</span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>i:s:j 指明第i位或第j位之间的子序列。当然，0
£ i £ j £ |s|。子序列0 : s : i 称为前缀，即prefix(s,i)，而子序列 i:s:|s| 称为后缀suffix(s,
|s|-i+1)。有两种特殊的情况，即 i=j或i = j-1。</span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>① i:s:i 表示空序列 </span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>② ( j-1):s: j 表示s
中的第j 个字符，简记为sj 。<O:P> </O:P></span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>一般认为，子序列与计算机算法中子串的概念相当。但是，严格地讲，子序列与子串的概念是有区别的：子串是子序列，而子序列不一定是子串。可以通过选取<span
lang=EN-US>s中的某些字符（或删除s中的某些字符）而形成s的子序列，例如TTT是ATATAT的子序列。而s的子串则是由s中相继的字符所组成，例如TAC是AGTACA的子串，但不是TTGAC的子串。如果t是s的子串，则称s是t的超串。子串也可以称为连续子序列。</span></span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>两条序列<span lang=EN-US>s和t的连接用s
+ + t来表示，如：</span></span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>
ACC++CTA = ACCCTA</span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>字符串操作除连接操作之外，另有一个<span
lang=EN-US>k操作，即删除一个字符串两端的字符。其定义如下：</span></span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>
prefix(s,l) = sk|s|-l ，</span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>
suffix(s,l) = k|s|-ls ，</span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>
i:s:j = ki-1sk|s|-j 。</span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>序列比较可以分为四种基本情况，具体任务和应用说明如下：</span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>（<span lang=EN-US>1）
假设有两条长度相近的、来自同一个字母表的序列，它们之间非常相似，仅仅是有一些细微的差别，例如字符的插入、字符的删除和字符替换，要求找出这两条序列的差别。这种操作实际应用比较多，例如，有两个实验室同时测定某个基因的DNA序列，其结果可能不一样，需要通过序列比较来比较实验结果。</span></span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>（<span lang=EN-US>2）
假设有两条序列，要求判断是否有一条序列的前缀与另一条序列的后缀相似，如果是，则分别取出前缀和后缀。该操作常用于大规模DNA测序中序列片段的组装。</span></span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>（<span lang=EN-US>3）
假设有两条序列，要求判断其中的一条序列是否是另一条序列的子序列。这种操作常用于搜索特定的序列模式。</span></span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>（<span lang=EN-US>4）
假设有两条序列，要求判断这两条序列中是否有非常相似的子序列。这种操作可用于分析保守序列。</span></span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>当然，进行序列比较时，往往还需要说明是采取全局比较，还是采取局部比较。全局比较是比较两条完整的序列，而局部比较是找出最大相似的子序列。</span><span
lang=EN-US><o:p></o:p></span></p>
<p><b><span lang=EN-US style='color:#EFCE8F'>3.1.2 编辑距离（Edit Distance） </span></b><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><V:SHAPETYPE id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" u1:preferrelative="t" u1:spt="75" coordsize="21600,21600"><V:STROKE joinstyle="miter"><V:FORMULAS><V:F eqn="if lineDrawn pixelLineWidth 0"><V:F eqn="sum @0 1 0"><V:F eqn="sum 0 0 @1"><V:F eqn="prod @2 1 2"><V:F eqn="prod @3 21600 pixelWidth"><V:F eqn="prod @3 21600 pixelHeight"><V:F eqn="sum @0 0 1"><V:F eqn="prod @6 1 2"><V:F eqn="prod @7 21600 pixelWidth"><V:F eqn="sum @8 21600 0"><V:F eqn="prod @7 21600 pixelHeight"><V:F eqn="sum @10 21600 0"></V:F></V:F></V:F></V:F></V:F></V:F></V:F></V:F></V:F></V:F></V:F></V:F></V:FORMULAS><V:PATH u1:connecttype="rect" gradientshapeok="t" u1:extrusionok="f"><O:LOCK aspectratio="t" u2:ext="edit"></O:LOCK></V:PATH></V:STROKE></V:SHAPETYPE><V:SHAPE id="_x0000_s1026" style="HEIGHT: 46.5pt; LEFT: 0px; MARGIN-LEFT: 142.8pt; MARGIN-TOP: 50pt; POSITION: absolute; TEXT-ALIGN: left; WIDTH: 126.75pt; Z-INDEX: 1" type="#_x0000_t75"><V:IMAGEDATA u1:title="" src="file:///C:/WINDOWS/TEMP/msoclip1/01/clip_image001.png"></V:IMAGEDATA></V:SHAPE><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>观察这样两条<span lang=EN-US>DNA序列：GCATGACGAATCAG和TATGACAAACAGC。一眼看上去，这两条序列并没有什么相似之处，然而如果将第二条序列错移一位，并对比排列起来以后，就可以发现它们的相似性。</span></span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText align=center style='text-align:center;text-indent:21.25pt;
line-height:150%'><span lang=EN-US><!--[if gte vml 1]><v:shape id="_x0000_i1027"
type="#_x0000_t75" alt="" style='width:120pt;height:47.25pt'>
<v:imagedata src="./第三章.files/image005.png" o:href="http://www.lmbe.seu.edu.cn/chenyuan/xsun/bioinfomatics/web/images/77.bmp"/>
</v:shape><![endif]--><![if !vml]><img border=0 width=160 height=63
src="./第三章.files/image006.jpg" v:shapes="_x0000_i1027"><![endif]><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>如果进一步在第二条序列中加上一条短横线，就会发现原来这两条序列有更多的相似之处。</span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText align=center style='text-align:center;text-indent:21.25pt;
line-height:150%'><span lang=EN-US><!--[if gte vml 1]><v:shape id="_x0000_i1028"
type="#_x0000_t75" alt="" style='width:173.25pt;height:47.25pt'>
<v:imagedata src="./第三章.files/image007.png" o:href="http://www.lmbe.seu.edu.cn/chenyuan/xsun/bioinfomatics/web/images/78.bmp"/>
</v:shape><![endif]--><![if !vml]><img border=0 width=231 height=63
src="./第三章.files/image008.jpg" v:shapes="_x0000_i1028"><![endif]><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>上面是两条序列相似性的一种定性表示方法，为了说明两条序列的相似程度，还需要定量计算。有两种方法可用于量化两条序列的相似程度：一为相似度，它是两条序列的函数，其值越大，表示两条序列越相似；与相似度对应的另一个概念是两条序列之间的距离，距离越大，则两条序列的相似度就越小。在大多数情况下，相似度和距离可以交互使用，并且距离越大，相似度越小，反之亦然。但一般而言，相似度使用得较多，并且灵活多变。</span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>最简单的距离就是海明（<span lang=EN-US>Hamming）距离。对于两条长度相等的序列，海明距离等于对应位置字符不同的个数。例如，</span></span><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt;color:blue'>图<span
lang=EN-US>3.1</span></span><span style='font-size:10.0pt;mso-bidi-font-size:
10.5pt'>是<span lang=EN-US>3组序列海明距离的计算结果。</span></span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText align=center style='text-align:center;text-indent:21.25pt;
line-height:150%'><span lang=EN-US><!--[if gte vml 1]><v:shape id="_x0000_i1029"
type="#_x0000_t75" alt="" style='width:315pt;height:99pt'>
<v:imagedata src="./第三章.files/image009.png" o:href="http://www.lmbe.seu.edu.cn/chenyuan/xsun/bioinfomatics/web/images/79.bmp"/>
</v:shape><![endif]--><![if !vml]><img border=0 width=420 height=132
src="./第三章.files/image010.jpg" v:shapes="_x0000_i1029"><![endif]><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>使用距离来计算不够灵活，这是因为序列可能具有不同的长度，两条序列中各位置上的字符并不一定是真正的对应关系。例如，在<span
lang=EN-US>DNA复制的过程中，可能会发生像删除或插入一个碱基这样的错误，虽然两条序列的其他部分相同，但由于位置的移动导致海明距离的失真。就图3.1中例子最右边的情况，海明距离为6，简单地从海明距离来看，两条序列差别很大（整个序列的长度只有8bp），但是，如果从s中删除G，从t中删除T，则两条序列都成为ACACACA，这说明两条序列仅仅相差两个字符。实际上，在许多情况下，直接运用海明距离来衡量两条序列的相似程度是不合理的。</span></span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>为了解决字符插入和删除问题，引入字符<span
lang=EN-US>“编辑操作”（Edit Operation）的概念，通过编辑操作将一个序列转化为一个新序列。用一个新的字符“-”代表空位（或空缺，Space），并定义下述字符编辑操作：</span></span><span
lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>
Match（a，a） — 字符匹配；</span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>
Delete（a，-） — 从第一条序列删除一个字符，或在第二条序列相应的位置插入空白字符；</span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>
Replace（a，b） — 以第二条序列中的字符b替换第一条序列中的字符a，a¹b；</span><span lang=EN-US><o:p></o:p></span></p>
<p class=MsoPlainText style='text-indent:21.25pt;line-height:150%'><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:10.5pt'>
Insert（-，b） — 在第一条序列插入空位字符，或删除第二条序列中的对应字符b。</span><span lang=EN-US><o:p></o:p></span></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -