DNA solution based on sequence alignment to the Minimum Spanning Tree problem. (19th May 2008)

• Record Type: Journal Article
• Authors: Han, Aili; Zhu, Daming; Pan, Jingchang
• Is Part Of: International journal of bioinformatics research and applications. Volume 4:Number 2(2008)
• Page Start: 188
• Page End: 200
• Publication Date: 2008-05-19
• Subjects: DNA computing -- sequence alignment -- DNA algorithms -- intelligent computation -- minimum spanning tree -- MST problem -- bioinformatics -- complement alignment -- reverse complement alignment -- DNA encoding -- optimisation; Bioinformatics -- Periodicals; 570.285
• Languages: English
• ISSNs: 1744-5485

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.