A Task Scheduling Method for Biological Gene Multi Sequence Alignment Algorithm

doi:10.3969/j.issn.1006-2475.2024.07.002

Abstract

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

CLC Number:

TP399

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.

References

［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]	ZHENG Jiuchao, ZHAO Xinyuan. Entity Linking Method Based on Topics and Description Information [J]. Computer and Modernization, 2024, 0(12): 10-14.
[2]	ZHAO Chenyang, XUE Tao, LIU Junhua. Fashion Clothing Pattern Generation Based on Improved Stable Diffusion [J]. Computer and Modernization, 2024, 0(12): 15-23.
[3]	WANG Xiaohang1, LI Yongjie1, YU Lei1, FAN Xiao2. A Method of Using Compound Event Probability Operation to Solve Problem of Negative Information Blocking Maximization [J]. Computer and Modernization, 2024, 0(12): 24-33.
[4]	ZHANG Xiaodong1, BAI Guangzhi1, LI Min1, LI Haoyang2. Oil and Gas Well Production Prediction Model Based on Empirical Wavelet Transform [J]. Computer and Modernization, 2024, 0(12): 53-58.
[5]	LIU Yunhai1, Feng Guang1, WU Xiaoting2, YANG Qun2 . Safety Helmet Wearing Detection Algorithm for Complex Construction Scenes [J]. Computer and Modernization, 2024, 0(12): 66-71.
[6]	LIU Baobao, YANG Jingjing, TAO Lu, WANG Heying . DSMSC Based on Attention Mechanism for Remote Sensing Image Scene Classification [J]. Computer and Modernization, 2024, 0(12): 72-77.
[7]	GU Yue, DENG Songfeng, SHEN Ji, MU Wentao, ZHAO Enqi. SAR Ship Detection Algorithm Based on Improved YOLOv8 [J]. Computer and Modernization, 2024, 0(12): 78-83.
[8]	WU Xiuling1, ZHOU Sheng1, WANG Chunjuan1, YU Cuizhuo2, LIU Hao3. Research Progress in Ultra Short-term Power Load Forecasting Technology [J]. Computer and Modernization, 2024, 0(12): 108-115.
[9]	LI Deyou1, 2, YU Jinsongdi1, 2, WEI Dandan1, 2, LUO Yuan1, 2, TONG Ruiju3. Abstract Tree Model for Gridded Cube Metadata [J]. Computer and Modernization, 2024, 0(11): 1-6.
[10]	GONG Yicheng1, 2, LIU Qing1, 2. Beijing Opera Binary Classification Based on RF-LCE-BiLSTM-Attention-AMSSA Model [J]. Computer and Modernization, 2024, 0(11): 7-12.
[11]	LI Taoying, LI Meng, WU Mengqiao. Taxi Passenger Flow Prediction Based on Heterogeneous Spatiotemporal Graph#br# Convolutional Networks [J]. Computer and Modernization, 2024, 0(11): 13-18.
[12]	ZHANG Tai1, YAN Zihao2, DUAN Jie2, ZHANG Zhihong2. Information Forwarding Strategy of Internet of Vehicles in Named Data Network [J]. Computer and Modernization, 2024, 0(11): 19-27.
[13]	YUAN Qingle, MU Li. Inventory Forecasting Method Based on Improved Elman Neural Network [J]. Computer and Modernization, 2024, 0(11): 28-33.
[14]	ZHANG Kun1, ZHANG Yongwei1, WU Yongcheng1, ZHANG Xiaowen2, ZHAI Shichen2. An LLM-based Method for Automatic Construction of Equipment Failure Knowledge Graphs [J]. Computer and Modernization, 2024, 0(11): 46-53.
[15]	YE Xue, YANG Sheng, CHENG Kai, ZHU Feng. A Financial Knowledge Q&A Model for Power Enterprise Based on ChatGLM2-6B [J]. Computer and Modernization, 2024, 0(11): 54-63.