The application of binary path matrix in backtracking of sequences alignment

DOI

10.2991/iceeecs-16.2016.58How to use a DOI?

Keywords

binary path matrix; dynamic programming; sequence alignment; backtracking.

Abstract

The sequence alignment is an extremely useful tool for molecular and evolutionary biology, and several programs and algorithms have developed for this purpose. The dynamic programming still keeps the most important position due to its highest accuracy, however, the accuracy of the algorithm is obtained by inserting or deleting some bases at the expense of possibly changing the basic or primary information of the original bases, it will lead to large errors in the prediction of the structure and function. This paper proposed an optimization algorithm based on the backtracking of the binary path matrix which is suitable for both global double sequence alignment and local sequence alignment. A scoring matrix is constructed based on the dynamic programming algorithm and a binary path matrix which is constructed at the same time. Then, the backtracking paths are extracted from the path matrix based on backtracking algorithm, and each backtracking path represents a alignment results. In this algorithm, global and local sequence alignment can be conducted at the same time. Compared with other sequence alignment algorithms, our proposed method can find more bases which are the same ones and provide better basis for analyzing the similarity of sequences.

Copyright

© 2016, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Zhongxi Cai
AU  - Chengzhen Xu
AU  - Ying Wang
AU  - Wang Cong
PY  - 2016/12
DA  - 2016/12
TI  - The application of binary path matrix in backtracking of sequences alignment
BT  - Proceedings of the 2016 4th International Conference on Electrical & Electronics Engineering and Computer Science (ICEEECS 2016)
PB  - Atlantis Press
SP  - 268
EP  - 275
SN  - 2352-538X
UR  - https://doi.org/10.2991/iceeecs-16.2016.58
DO  - 10.2991/iceeecs-16.2016.58
ID  - Cai2016/12
ER  -