文章基本信息

标题：Bit-Parallelism Score Computation with Multi Integer Weight
本地全文：下载
作者：Setyorini ; Kuspriyanto ; Dwi Hendratmo Widyantoro 等
期刊名称：International Journal on Electrical Engineering and Informatics
印刷版ISSN：2085-6830
出版年度：2019
卷号：11
期号：1
页码：35-50
DOI：10.15676/ijeei.2019.11.1.3
出版社：School of Electrical Engineering and Informatics
摘要：Dynamic Programming (DP) is still the core algorithm in many biological analysistools, especially similarity analysis. DP always promises optimal solutions, but as the size andnumber of sequences increase, time performance decreases. This makes various researchesrelated to the improvement of time performance offered. Performance improvement is offeredby adding process units that work together in parallel environments or reducing the accuracy byonly calculating the input part. Bit-parallelism offers an increase in speed by changing the scorematrix process unit to a larger process unit, namely word. Then this word unit will be processedin parallel like word processing on a computer system. Bit-parallelism has been successfullyapplied to cases with simple weights such as LCS and Edit Distance. Applications in morecomplex cases, namely with integer weights also exist, but still assume an integer weight formatch representation. In the case of protein alignment where there is more than one integer valueto represent the match of the residual pair, this solution cannot be applied directly. This paperpresents a preliminary research on how to formulate a computational algorithm score bitparallelismwith multi-integer weights. The solution offered is the development of GeneralInteger scoring, by applying functional multi tables. The results show that the algorithm is ableto obtain the same score matrix as the DP score matrix, with computing 𝑂(𝑚), m is size of thesequence, and 𝑂(𝑏) space where 𝑏 is the range of integer set weights.
关键词：Sequence Alignment; Dynamic Programming; Bit-Parallelism; General Integer;Scoring.