Title: DNA solution based on sequence alignment to the Minimum Spanning Tree problem

Authors: Aili Han, Daming Zhu, Jingchang Pan

Addresses: Department of Computer Science and Technology, Shandong University at Weihai, Weihai 264209, China. ' School of Computer Science and Technology, Shandong University, Jinan 250061, China. ' Department of Computer Science and Technology, Shandong University at Weihai, Weihai 264209, China

Abstract: Sequence alignment reveals the relations between the characters in different sequences, and there are the reverse complement relations between the characters in DNA double strand. We introduce sequence alignment to the field of DNA computing, propose the definitions of complement alignment and reverse complement alignment, give a method of computing the scores of complement alignment and reverse complement alignment, and devise a DNA encoding method and the corresponding DNA algorithm for the Minimum Spanning Tree (MST) problem by means of reverse complement alignments. Our work enriches the theory of DNA computing and extends the range of DNA computing to solve optimisation problems.

Keywords: DNA computing; sequence alignment; DNA algorithms; intelligent computation; minimum spanning tree; MST problem; bioinformatics; complement alignment; reverse complement alignment; DNA encoding; optimisation.

DOI: 10.1504/IJBRA.2008.018345

International Journal of Bioinformatics Research and Applications, 2008 Vol.4 No.2, pp.188 - 200

Published online: 17 May 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article