基于多策略人工蜂群的多序列比对算法资源-CSDN文库

198 浏览量 2021-01-13 00:57:34 上传评论收藏 242KB PDF 举报

资源推荐

资源详情

资源评论

第 33卷第 11期控制与决策 Vol.33 No.11

2018年 11月 Control and Decision Nov. 2018

文章编号: 1001-0920(2018)11-1990-07 DOI: 10.13195/j.kzyjc.2017.0788

基于多策略人工蜂群的多序列比对算法

匡芳君

1,2†

, 张思扬

, 刘传才

(1. 温州商学院信息工程学院，浙江温州 325035；2. 南京理工大学计算机科学与工程学院，南京 210094)

摘要: 多序列比对是生物信息学中最重要和最具挑战性的任务之一. 基于多序列比对是NP 完全组合优化问题,

引入Tent 混沌初始化种群策略、不同蜂种的邻域搜索策略和锦标赛选择策略等,提出一种基于多策略人工蜂群的

多序列比对算法. 该算法应用 Tent混沌初始化种群策略以使初始个体多样化并获取较好初始解; 针对不同蜂种的

特性设计不同的邻域搜索策略以平衡算法的全局探索和局部开发能力. 同时引入序列比对的蜜源编码方法以适

应多序列比对的离散性. 实验结果表明,所提出算法的鲁棒性较强,能获取较好的比对性能和生物特性.

关键词: 人工蜂群算法；多策略；Tent混沌初始化；邻域搜索；多序列比对

中图分类号: TP18 文献标志码: A

Multiple sequence alignment algorithm based on multi-strategy artiﬁcial

bee colony

KUANG Fang-jun

1,2†

, ZHANG Si-yang

, LIU Chuan-cai

(1. School of Information Engineering，Wenzhou Business College，Wenzhou 325035，China；2. School of Computer

Science and Engineering，Nanjing University of Science and Technology，Nanjing 210094，China)

Abstract: Multiple sequence alignment(MSA), known as NP-complete combinatorial optimization problem, is one of

the most important and challenging tasks in bioinformatics. A multi-strategy artiﬁcial bee colony(MS-ABC) algorithm is

proposed for MSA, which is composed of multiple strategies, such as the Tent chaotic initialization population strategy,

diﬀerent neighborhood search strategies and tournament selection strategy. In the MSA-ABC algorithm, the Tent chaotic

initialization population strategy is presented to diversify the initial individuals and to obtain good initial solutions. Then,

the diﬀerent neighborhood search strategies for diﬀerent bee species are designed to balance the global exploration and the

local exploitation. Moreover, the food source encoding method is used to adapt discreteness of MSA. The experimental

results demonstrate that the proposed algorithm is more robust and can obtain better alignment quality and biological

characteristics.

Keywords: artiﬁcial bee colony；multi-strategy；Tent chaotic initialization；neighborhood search；multiple sequence

alignment

0 引言

多序列比对 (Multiple sequence alignment, MSA)

是生物信息学研究的热点之一,通过多序列比对可以

挖掘生物序列中的结构、进化和功能等信息, MSA也

是一个 NP完全组合优化难题

[1]

. 自然启发式算法作

为一类适用于求解 NP难题的优化算法,具有精度高、

对度量标准不敏感等优势, 吸引着大量研究人员,其

研究成果颇丰. 如 Gupta等

[2]

提出了一种基于遗传算

法的多序列比对方法 (MSA-GA); Gao

[3]

提出了一种

基于惯性权重粒子群优化算法 (MS-PSO); Tsvetanov

等

[4]

提出了一种基于改进蚁群算法的多序列比对方

法 (MS-ACO); Öztürk等

[5]

提出了一种新的人工蜂群

算法的多序列比对方法(ABC-Aligner); Zhu等

[6]

提出

了一种基于分解的多目标进化算法 (MOMSA) 以解

决多序列比对问题, 初始种群通过使用空位插入操

作生成,进化操作利用遗传操作的交叉和变异算子实

现; Liu等

[7]

提出了一种基于隐马尔可夫模型和后验

概率分配函数的多序列比对算法 (MSAProbs); Rani

等

[8]

提出了基于遗传和人工蜂群的混合算法 (GA-

ABC) 和多目标细菌觅食优化算法 (MO-BFO), 并应

收稿日期: 2017-06-20；修回日期: 2017-08-22.

基金项目: 国家自然科学基金项目(61373063, 61233011, 61402227).

责任编委: 巩敦卫.

作者简介: 匡芳君 (1976−), 女, 教授, 博士, 从事群智能与多目标优化、模式识别、生物信息学及其应用等研究；刘

传才 (1963−), 男, 教授, 博士生导师, 从事智能计算、计算机视觉、图像处理及应用等研究.

†

通讯作者. E-mail: kfjztb@126.com

第

期

匡芳君等

基于多策略人工蜂群的多序列比对算法

1991

用于多序列比对, 但在工作中主要集中于 MO-BFO

算法; Sun等

[9]

提出了一种基于量子粒子群优化和隐

马尔可夫模型的多序列比对算法; Rubio-Largo 等

[10]

结合多目标和进化启发式算法,提出了一种基于混合

蛙跳算法的多序列比对方法; Zambrano-Vega等

[11]

进

行了基于多目标启发式算法的多序列比对方法的比

较研究,并对这些启发式方法进行了综述和比较.

人工蜂群算法 (Ar tiﬁcial bee colony, ABC) 是由

Karaboga于 2005 年提出的群智能算法

[12]

,具有全局

探索能力强、控制参数少、收敛速度快和鲁棒性强等

优势,被广泛应用于求解复杂优化问题

[13]

,但当其接

近全局最优解时,种群多样性减少,搜索速度变慢,甚

至易陷入局部最优,因此也衍生了很多改进算法和应

用

[14-16]

. 本文在研究多序列比对算法作为多目标优

化问题的基础上,在人工蜂群算法中引入 Tent混沌初

始化种群策略、不同蜂种的邻域搜索策略和锦标赛

选择策略等,提出了一种基于多策略人工蜂群的多序

列比对算法.

1 多序列比对优化模型

多序列比对主要反映给定序列之间的进化关

系. 目的是使参与比对的序列尽可能相似 (或距离最

小), 即相同残基的位点位于同一列. 多序列比对问

题描述如下

[6]

:假设参与比对的序列组 S = ( S

, S

· · ·

, S

)

含有

条序列

每条序列长度分别为

, · · · , l

, 序列中字符由 4种核苷酸或 20 种氨基酸

组成. 通过插入或删除空位找到一个多序列比对S

′

使对齐的字符数最多. 多序列比对 S

′

的约束条件

为: 1) S

′

中各条比对后的序列长度相等; 2) 若删除

′

中的第 i 行所有空位, 则 S

′

= S

; 3) 使多序列比对

′

的评分Score(S

′

)最大.

多序列比对常用目标函数主要有: WSP 权重计

分函数,隐Markov模型, COFFEE计分函数等

[6]

. 本文

采用WSP函数,其评分函数Score(S

′

)表示为

Score(S

′

) =

∑

l=1

′

. (1)

′

N−1

∑

i=1

∑

k=i+1

p(A

, A

). (2)

p(A

, A

) =











0, A

= A

′

−

′

;

−g

open

, (A

′

−

′

and A

=

′

−

′

) or

=

′

−

′

and A

′

−

′

) and is opening;

−g

extend

, (A

′

−

′

and A

=

′

−

′

) or

=

′

−

′

and A

′

−

′

) and is extension;

Blosum(A

, A

), A

=

′

−

′

and A

=

′

−

′

(3)

其中: L 为多序列比对S

′

的长度; S

′

为多序列比对 S

′

第l 列的代价; N 为序列比对组中序列的条数; w

为

序列 s

和 s

的权重, 取决于序列间的距离,本文利用

编辑距离 (Levenshtein distance, LD)来计算w

,令w

= 1 −

LD(s

, s

)

max(|s

|, |s

,其中max(|s

|, |s

|)为两条序列

和 s

长度的最大值; p(A

, A

) 为序列中残基 A

和

的评分; g

open

, g

extend

分别为单位空位开放罚分和

单位空位扩展罚分; Blosum(A

, A

)为根据残基片段

替换矩阵(Blocks substitution matrix)计算残基匹配评

分

[6]

. 使序列间匹配的残基对个数最大, 而空位罚分

最小是多序列比对追求的目标,故多序列比对多目标

优化函数表示如下:

max imize F (S

′

) = (f

′

), f

′

))

′

) = Score(S

′

) = − g(S

′

∈ Ω. (4)

其中: g(S

′

) = n

× g

open

+ n

× g

extend

为对齐序

列组 S

′

的空位罚分, n

, n

分别为空位开放的数量

和空位扩展的数量; Ω 为多序列比对空间. 本文选用

Blosum 62替换矩阵, g

open

= 6, g

extend

= 0.85.

例 1 假设参与比对的序列组为 S, 通过序列比

对后得到的对齐序列比对为S

′

,结果如图1所示.

Seq1:NFS

Seq2:NYLS

Seq3:NKYLS

Seq4:NFLS

Seq1:NF--S

Seq2:NY-LS

Seq3:NKYLS

Seq4:NF-LS

’

Alignment

Algorithm

图 1 多序列比对实例

1) 计算序列组 S 中每一对序列间的权重 w

,即

= 1 −

LD(s

, s

)

max(|s

|, |s

= 1 −

= 0.5. 同理, w

0.4, w

= 0.75, w

= 0.8, w

= 0.75, w

= 0.6.

2) 按式(3)和(4)计算序列S

′

每一列代价值,即

′

× p(S

′

, S

′

) + w

× p(S

′

, S

′

× p(S

′

, S

′

) + w

× p(S

′

, S

′

× p(S

′

, S

′

) + w

× p(S

′

, S

′

) =

(0.5 × Blosum(N, N)) + (0.4 × Blosum(N, N ))+

(0.75 × Blosum(N, N)) + (0.8 × Blosum(N, N ))+

(0.75 × Blosum(N, N)) + (0.6 × Blosum(N, N )) =

22.8.

同理, S

′

= 3.45, S

′

= −10.8, S

′

= 7.197 5, S

′

15.2.

3) 按式 (1) 计算对齐序列 S

′

的评分 Score(S

′

) =

37.847 5.

剩余6页未读，继续阅读

评论收藏

内容反馈

weixin_38681646

粉丝: 6
资源: 882

基于多策略人工蜂群的多序列比对算法

人工蜂群算法

人工蜂群算法的研究与应用_人工蜂群matlab_人工蜂群_人工蜂群算法_人工蜂群算法论文介绍_matlab_

基于matlab的人工蜂群算法

基于人工蜂群的BP神经网络 人工蜂群算法的反向传播神经网络.zip

ABC2_MATLAB_人工蜂群_人工蜂群算法_蜂群路径规划

基于MATLAB的人工蜂群算法

python实现人工蜂群算法

基于分布式禁忌人工蜂群算法的云视频直播优化算法.pdf

人工蜂群算法matlab程序

人工蜂群算法以及测试函数

基于人工蜂群算法的Tor流量在线识别方法_梁晓萌_人工蜂群算法_

基于混沌的人工蜂群算法

人工蜂群.zip_人工蜂群_人工蜂群优化_人工蜂群算法_蜂群_蜂群算法

人工蜂群算法c程序及详细解释

基于改进人工蜂群算法的机器人路径规划

人工蜂群算法ABC源码，MATLAB实现

基于人工蜂群算法的函数优化分析.zip

最新资源

基于人工蜂群的BP神经网络人工蜂群算法的反向传播神经网络.zip