Open AccessA Greedy Clustering Algorithm for Multiple Sequence Alignment
Publication year - 2021
Publication title -
international journal of cognitive informatics and natural intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.164
H-Index - 24
eISSN - 1557-3966
pISSN - 1557-3958
DOI - 10.4018/ijcini.20211001oa28
Subject(s) - computer science , sequence (biology) , cluster analysis , set (abstract data type) , multiple sequence alignment , sequence alignment , divide and conquer algorithms , greedy algorithm , algorithm , theoretical computer science , artificial intelligence , biochemistry , genetics , chemistry , gene , peptide sequence , biology , programming language
This paper presents a strategy to tackle the Multiple Sequence Alignment (MSA) problem, which is one of the most important tasks in the biological sequence analysis. Its role is to align the sequences in their entirety to derive relationships and common characteristics between a set of protein or nucleotide sequences. The MSA problem was proved to be an NP-Hard problem. The proposed strategy incorporates a new idea based on the well-known divide and conquer paradigm. This paper presents a novel method of clustering sequences as a preliminary step to improve the final alignment; this decomposition can be used as an optimization procedure with any MSA aligner to explore promising alignments of the search space. In their solution, authors proposed to align the clusters in a parallel and distributed way in order to benefit from parallel architectures. The strategy was tested using classical benchmarks like BAliBASE, Sabre, Prefab4 and Oxm, and the experimental results show that it gives good results by comparing to the other aligners.