Proceedings of the 2016 4th International Conference on Electrical & Electronics Engineering and Computer Science (ICEEECS 2016)

The application of binary path matrix in backtracking of sequences alignment

Authors
Zhongxi Cai, Chengzhen Xu, Ying Wang, Wang Cong
Corresponding Author
Zhongxi Cai
Available Online December 2016.
DOI
https://doi.org/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.
Open Access
This is an open access article distributed under the CC BY-NC license.

Download article (PDF)

Proceedings
2016 4th International Conference on Electrical & Electronics Engineering and Computer Science (ICEEECS 2016)
Part of series
Advances in Computer Science Research
Publication Date
December 2016
ISBN
978-94-6252-265-7
ISSN
2352-538X
DOI
https://doi.org/10.2991/iceeecs-16.2016.58How to use a DOI?
Open Access
This is an open access article distributed under the CC BY-NC license.

Cite this article

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  - 2016 4th International Conference on Electrical & Electronics Engineering and Computer Science (ICEEECS 2016)
PB  - Atlantis Press
SN  - 2352-538X
UR  - https://doi.org/10.2991/iceeecs-16.2016.58
DO  - https://doi.org/10.2991/iceeecs-16.2016.58
ID  - Cai2016/12
ER  -