DNA algorithm of minimal spanning tree

Zhixiang Yin; Linqiang Pan; Xiaohong Shi

doi:10.1117/12.718220

30 October 2006 DNA algorithm of minimal spanning tree

Zhixiang Yin, Linqiang Pan, Xiaohong Shi

Proceedings Volume 6358, Sixth International Symposium on Instrumentation and Control Technology: Sensors, Automatic Measurement, Control, and Computer Simulation; 63584O (2006) https://doi.org/10.1117/12.718220
Event: Sixth International Symposium on Instrumentation and Control Technology, 2006, Beijing, China

Abstract

Minimum spanning tree is one of important problem in graph theory and has a variety of applications. Kruskal's adding edge and cutting cycle methods are routinely and commonly used method when finding a minimum spanning tree of a specific graph. However, the two methods require determining whether adding edge or cutting cycle will induce cycle at every step during the course of computation. This paper present a new method to solve the minimum spanning tree prblem by means of encoding the graph in DNA strands and employing conventional biological manipulations, such as, electrophoresis, sequencing,etc. The proposed method can avoid the drawback of Kruskal's methods, moreover, the time complexity of proposed method is Ο(n), and the amount of DNA strands required for encoding is m n + ( n is the number of vertices and m is the number of edges of the graph).

Citation Download Citation

Zhixiang Yin, Linqiang Pan, and Xiaohong Shi "DNA algorithm of minimal spanning tree", Proc. SPIE 6358, Sixth International Symposium on Instrumentation and Control Technology: Sensors, Automatic Measurement, Control, and Computer Simulation, 63584O (30 October 2006); https://doi.org/10.1117/12.718220

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available