title: DNA solution based on sequence alignment to the Minimum Spanning Tree problem.
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.
authors.affiliation: Department of Computer Science and Technology, Shandong University at Weihai, Weihai, China. hanal@sdu.edu.cn
authors.forename: Aili
authors.initials: A
authors.lastname: Han
authors.forename: Daming
authors.initials: D
authors.lastname: Zhu
authors.forename: Jingchang
authors.initials: J
authors.lastname: Pan
mesh_terms: D000465:Algorithms; D004247:DNA / Q000737:chemistry* / Q000235:genetics; D016415:Sequence Alignment
chemical_list: D004247:DNA