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/).
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 - 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 -