Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 生物信息学笔记（三）
发信站: 哈工大紫丁香 (2001年06月08日18:50:50 星期五), 站内信件

§3 最短超串问题
一 问题定义
给定串的集合P={S1,S2,...,Sk}，求最短串S*(P)，是P中每个串的超串.
简称SSP.已知SSP是MAX SNP hard的(从而也是NP hard).
1,...,k的每一个置换Π规定了P的一个超串S(Π).问题归结为求最优置换.
对串Si,Sj,用ov(Si,Sj)表示Si,Sj重叠部分的最大长度,p(Si,Sj)=Si-ov(Si,Sj).
pref(Si,Sj)表示Si长度为p(Si,Sj)的前缀.
设Π=o1o2...ot,则
       k-1
|S(Π)|=Σ  p(S oi , S oi+1) + |S ok|
       i=1
             k-1
      =|P| -  Σ ov(S oi , S oi+1)
             i=1
问题转化成求
     k-1
      Σ ov(S oi , S oi+1)
     i=1
最大问题.
串S的圈串记为φ(S),P的圈覆盖记为C(P),最短圈覆盖为C*(P).
对圈串C*(P),用Pφ表示P中与关联的串的子集.
用Lφ=o1o2...ot表示Pφ中的串按照在φ上的起始位置的次序的序号排列.
S(Lφ)=pref(So1,S o2)pref(S o2, S o3)...pref(ot-1,S ot) S ot.
用L'φ表示L的循环移位.如果oi是L'φ的最后一个序号,称S oi是S(L'φ)的
结尾串.
引理 如果S oi是S(L'φ)的结尾串,则|S(L'φ)|=|φ|+ov(S oi,S oi+1).
二 最短圈覆盖
可以归结为最大完全指派问题.
如果P包含k个串,构造指派问题的实例,它的输入是k*k矩阵A,A(i,j)是一个自然数.
A的一个完全指派是A中的k个单元的集合M，每行及每列恰好有一个单元.M的权是
这些单元中的数的和.
M的一个圈定义为一个序号的集合{i1,i2,...,it},使得A(i1,i2),A(i2,i3)直到A(i t-1
,it)在M中.
令指派问题的每个序号i对应P中的串Si,M的每个圈对应一个圈串,A(i,j)设为ov(Si,Sj)
.
不难看出P的最短圈覆盖恰好对应A的最大完全指派.
对4-近似算法,相应指派问题的时间O(k^2 log k).
对3-近似算法,相应指派问题的时间O(k^3).
三 BJLTY算法
Blum,Jiang,Li,Tromp,Yannakakis提出.
猜想:贪心算法是2-近似算法.
例 P={c(ab)^k,(ba)^k,(ab)^k c}
贪心算法 c(ab)^k c (ba)^k 长度4k+2
最短超串 cab(ab)^(k-1)abc 长度2k+4
4-近似算法,3-近似算法.
基本思想:首先构造P的圈覆盖,然后打开圈串拼接成超串.
4-近似算法
(1)找P的最短圈覆盖C*(P);
(2)对C*(P)内的每一个圈φ,构造序号列Lφ和P的超串S(Lφ),这样得到的超串的集合记
为P';
(3)按照任意次序连接P'中的串得到P的超串H.
定义
非平凡圈覆盖,每个圈至少关联两个串.
3-近似算法
(1)找P的最短圈覆盖C*(P);
(2)对C*(P)内的每一个圈φ,构造序号列Lφ和P的超串S(Lφ),这样得到的超串的集合记
为P',
设P'={S'1,S'2,...,S'r};
(3)找P'的非平凡圈覆盖C*(P');
(4)对C*(P')内的每一个圈ρ,令Lρ=o1o2...ot,t>=2.是P'中的串按照在的起始位置的序
号表,
对Lρ的每个循环移位定义一个映射到的超串.取使超串最短的循环移位.就是选择oi∈L
ρ,使得
ov(s' oi,si' o i+1)最小,对Lρ进行移位使得s' oi为结尾串.这样得到的序号表为L'ρ
,构造相应的
串S(L'ρ),它是P'中与关联ρ的串的超串;
(5)连接上步得到的超串得到串H'(P).

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]