一种面向生物基因多序列比对算法的任务调度方法

doi:10.3969/j.issn.1006-2475.2024.07.002

摘要/Abstract

摘要： 摘要：针对现阶段生物基因多序列比对算法在面对大规模数据时存在比对效率慢的问题，提出一种面向生物基因多序列比对算法的任务调度方法，以提高生物基因多序列比对的效率。通过Trie树方法对生物基因多序列数据展开分割处理，从而提高后续基因多序列比对过程中数据查找和匹配的效率；构建基因多序列BWT索引，利用BWT索引方法完成生物基因多序列比对；以多序列比对方法为基础，采用CPU与GPU异构并行系统完成多序列比对的任务调度。实验结果表明，所提的面向生物基因多序列比对算法的任务调度方法效率更高、性能更好，且更适合于实际应用。

关键词: 生物基因, 任务调度, 多序列比对, CPU与GPU, BWT索引方法

Abstract: Abstract： Aiming at the problem of slow alignment efficiency in current biological gene multi sequence alignment algorithms when facing large-scale data， a task scheduling method for biological gene multi sequence alignment algorithms is proposed to improve the efficiency of biological gene multi sequence alignment. Firstly， the Trie tree method is used to segment biological gene multi sequence data， thereby optimizing the efficiency of data search and matching in the subsequent gene multi sequence alignment process; Secondly a gene multi sequence BWT index is constructed and the BWT index method is used to complete biological gene multi sequence alignment; Finally， based on the multi sequence alignment method， a heterogeneous parallel system of CPU and GPU is used to complete the task scheduling of multi sequence alignment. The experimental results show that the proposed task scheduling method for biological gene multi sequence alignment algorithm is more efficient， performs better， and is more suitable for practical applications.

Key words: , biological genes； task scheduling； multiple sequence alignment； CPU and GPU； BWT indexing method

中图分类号:

TP399

杨波, 王宏杰, 徐胜超, 毛明扬, 蒋金陵, 蒋大锐. 一种面向生物基因多序列比对算法的任务调度方法[J]. 计算机与现代化, 2024, 0(07): 7-12.

YANG Bo, WANG Hongjie, XU Shengchao, MAO Mingyang, JIANG Jinling, JIANG Darui. A Task Scheduling Method for Biological Gene Multi Sequence Alignment Algorithm[J]. Computer and Modernization, 2024, 0(07): 7-12.

参考文献

［1］ Shubham， PRAKASH S， GANAPATHI P. An algorithm for the sequence alignment with gap penalty problem using multiway divide-and-conquer and matrix transposition［J］. Information Processing Letters， 2022，173. DOI： 10.1016/j.ipl.2021.106166.
［2］ KILINC M， JIA K J， JERNIGAN R L. An improved protein sequence alignment algorithm scores pairs of substitutions［J］. Biophysical Journal， 2022，121（3）. DOI： 10.1016/j.bpj.2021.11.1827.
［3］潘登，钟诚. 二级Hash全局和局部索引筛选的长序列比对并行算法［J］.小型微型计算机系统， 2022，43（9）：1999-2004.
［4］冯晓龙，高静. 基于Spark的基因短序列比对模型［J］. 计算机仿真， 2020，37（2）：231-236.
［5］ FU Y， ZHOU W. A heterogeneous parallel implementation of the Markov clustering algorithm for large-scale biological networks on distributed CPU-GPU clusters［J］. The Journal of Supercomputing， 2022，78（7）：9017-9037.
［6］ SARKAR A， GHOSH S， RAY S S. A hardware-based memory-efficient solution for pair-wise compact sequence alignment［J］. IETE Journal of Research， 2023，69（6）：3638-3649.
［7］毋东，魏亚伟，罗军伟，等. 基于长读数和多序列比对的间隙填充方法［J］. 计算机工程， 2021，47（11）：93-99.
［8］季晓敏，沈益新，迟英俊. 蒺藜苜蓿MtPEAMT基因克隆及其序列比对分析［J］. 江苏农业科学， 2021，49（18）：54-64.
［9］ TANG W S， CRAWFORD L. Topological approach for sequence-independent protein structure alignment［J］. Biophysical Journal， 2022，121（3）. DOI： 10.1016/j.bpj.2021.
11.2045.
［10］甘秋云. 基于动态规划的Needleman-Wunsch双序列比对算法的分析与研究［J］. 计算机工程与科学， 2021，43（2）：340-346.
［11］王淋，钟诚. 水平聚类分簇和垂直分组的大规模长序列多比对［J］. 小型微型计算机系统， 2023，44（10）：2353-2361.
［12］ BZIKADZE A V， PEVZNER P A. UniAligner： A parameter-free framework for fast sequence alignment［J］. Nature Methods， 2023，20（9）：1346-1354.
［13］ ZHANG F F， MEI Y， NGUYEN S， et al. Multitask genetic programming-based generative hyperheuristics： A case study in dynamic scheduling［J］. IEEE Transactions on Cybernetics， 2022，52（10）：10515-10528.
［14］ LIU D， YANG S G， HE Z L， et al. CARTAD： Compiler-assisted reinforcement learning for thermal-aware task scheduling and DVFS on multicores［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2022，41（6）：1813-1826.
［15］ ZHOU C H， WU W， HE H L et al. Deep reinforcement learning for delay-oriented IoT task scheduling in SAGIN［J］. IEEE Transactions on Wireless Communications， 2021，20（2）：911-925.
［16］ LI C L， LIU J， LI W G， et al. Adaptive priority-based data placement and multi-task scheduling in geo-distributed cloud systems［J］. Knowledge-Based Systems， 2021，224. DOI： 10.1016/j.knosys.2021.107050.
［17］ ALSADIE D. A metaheuristic framework for dynamic virtual machine allocation with optimized task scheduling in cloud data centers［J］. IEEE Access， 2021，9：74218-74233.
［18］ KAMILIN M H B， AHMADON M A B， YAMAGUCHI S. Multi-task learning-based task scheduling switcher for a resource-constrained IoT system［J］. Information （Switzerland）， 2021，12（4）. DOI： 10.3390/info12040150.
［19］ ABDEL-BASSET M， MOHAMED R， ABOUHAWWASH M， et al. EA-MSCA： An effective energy-aware multi-objective modified sine-cosine algorithm for real-time task scheduling in multiprocessor systems： Methods and analysis［J］. Expert Systems with Applications， 2021，173（6）. DOI： 10.1016/j.eswa.2021.114699.
［20］ NIKSERESHT M， RAJI M. MOGATS： A multi-objective genetic algorithm-based task scheduling for heterogeneous embedded systems［J］. International Journal of Embedded Systems， 2021，14（2）：171-184.
［21］ FERREIRA M D， MELLO R F D. Time complexity evaluation of cover song identification algorithms［J］. Applied Acoustics， 2021，175. DOI： 10.1016/j.apacoust.2020.107777.
［22］ ZHANG F F， MEI Y， NGUYEN S， et al. Surrogate-assisted evolutionary multitask genetic programming for dynamic flexible job shop scheduling［J］. IEEE Transactions on Evolutionary Computation， 2021，25（4）：651-665.
［23］ OJHA V， ABRAHAM A， SNASEL V. Heuristic design of fuzzy inference systems： A review of three decades of research［J］. Engineering Applications of Artificial Intelligence， 2019，85：845-864.
［24］ MUSTAFI D， SAHOO G. A hybrid approach using genetic algorithm and the differential evolution heuristic for enhanced initialization of the k-means algorithm with applications in text clustering［J］. Soft Computing， 2019，23：6361-6378.
［25］ JOHNS M B， KEEDWELL E， SAVIC D. Knowledge-based multi-objective genetic algorithms for the design of water distribution networks［J］. Journal of Hydroinformatics， 2020，22（2）：402-422.
［26］ ALVARENGA W J， CAMPOS F V， HANRIOT V M， et al. Online learning of neural networks using random projections and sliding window： A case study of a real industrial process［J］. Engineering Applications of Artificial Intelligence， 2021，100（1）. DOI： 10.1016/j.engappai.2021.104181.
［27］ LI Z X， NIU C T， YANG X H， et al. Enhanced acidic resistance ability and catalytic properties of bacillus 1，3-1，4-β-glucanases by sequence alignment and surface charge engineering［J］. International Journal of Biological Macromolecules， 2021，192（12）：426-434.

[1]	王佳1, 顾文俊1, 鞠炜刚2, 李玉维1, 张云龙2, 米传民3, 周志鹏3. 基于多元级差优良化遗传算法的环境拓扑结构任务调度[J]. 计算机与现代化, 2024, 0(10): 65-73.
[2]	赵然1,2，郭志川1,2,朱小勇1,2. 一种基于Levy飞行的改进蝗虫优化算法[J]. 计算机与现代化, 2020, 0(01): 104-.
[3]	姜凯. 基于混沌人工蜂群的云计算任务调度算法[J]. 计算机与现代化, 2016, 0(6): 7-11.
[4]	满立1,朱瑞龙2. 多特征协调的实时调度算法[J]. 计算机与现代化, 2015, 0(2): 44-.
[5]	黄国兵1，蔺元2，金勇1. 基于现场适应性策略的自动抄表任务调度算法[J]. 计算机与现代化, 2015, 0(11): 36-39+46.
[6]	魏成巍，裴毅，刘东升，王卫平. 基于PSO的多无人机协同任务目标分配方法[J]. 计算机与现代化, 2015, 0(11): 32-35.
[7]	马亮;李晓. 基于改进粒子群算法的云计算任务调度策略[J]. 计算机与现代化, 2013, 1(9): 78-81,1.
[8]	王朋. 云计算环境下任务调度策略研究[J]. 计算机与现代化, 2013, 1(7): 22-025.
[9]	陈春雷. 一种GPU集群任务调度中间件的设计与实现[J]. 计算机与现代化, 2013, 1(2): 130-133.
[10]	贺智明,杨书金 . 基于DPSO的云工作流任务自适应调度策略[J]. 计算机与现代化, 2013, 12(12): 125-129.
[11]	李慧敏;张金辉. 基于改进DPSO的网格资源调度算法[J]. 计算机与现代化, 2012, 1(03): 30-33.
[12]	邓树强;刘波;庞雄文. 改进的Min-Min算法研究[J]. 计算机与现代化, 2011, 1(6): 76-4.
[13]	李慧敏;蒋秀凤. 基于QoS效益函数的网格任务调度算法 [J]. 计算机与现代化, 2009, 169(9): 12-14.