UM
Molecular solution to the optimal linear arrangement problem based on DNA computation
Liu X.2; Yang X.2; Tang Y.Y.2
2008-07-01
Source PublicationJournal of Mathematical Chemistry
ISSN02599791
Volume44Issue:1Pages:172-183
AbstractDue to massive parallelism, enormous memory storage and very low energy consumption, biomolecular operations have been suggested to solve various NP-hard problems that are beyond the capability of the fastest known digital computer. The optimal linear arrangement (OLA) problem is a well-known NP-hard combinatorial optimization problem. Based on a DNA computational model, this paper describes a novel algorithm for the OLA problem, which is executed in O(n log n) DNA operations on tubes of (nK + n + m + L + 1)-bits DNA strands, where K = ⌈ logn and L = ⌈ log (nm}⌉ + 1. With the advance in molecular biology techniques, this algorithm may be of practical utility. © 2007 Springer Science+Business Media, LLC.
KeywordAdleman-Lipton-sticker model DNA algorithm DNA computation NP-hardness Optimal linear arrangement problem
DOI10.1007/s10910-007-9299-6
URLView the original
Language英語
Fulltext Access
Citation statistics
Cited Times [WOS]:2   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionUniversity of Macau
Affiliation1.Logistical Engineering University China
2.Chongqing University
Recommended Citation
GB/T 7714
Liu X.,Yang X.,Tang Y.Y.. Molecular solution to the optimal linear arrangement problem based on DNA computation[J]. Journal of Mathematical Chemistry,2008,44(1):172-183.
APA Liu X.,Yang X.,&Tang Y.Y..(2008).Molecular solution to the optimal linear arrangement problem based on DNA computation.Journal of Mathematical Chemistry,44(1),172-183.
MLA Liu X.,et al."Molecular solution to the optimal linear arrangement problem based on DNA computation".Journal of Mathematical Chemistry 44.1(2008):172-183.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Liu X.]'s Articles
[Yang X.]'s Articles
[Tang Y.Y.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Liu X.]'s Articles
[Yang X.]'s Articles
[Tang Y.Y.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Liu X.]'s Articles
[Yang X.]'s Articles
[Tang Y.Y.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.