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