Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] [ 24]


Journal of Information Science and Engineering, Vol. 26 No. 2, pp. 333-346 (March 2010)

Testing Whether a Set of Code Words Satisfies a Given Set of Constraints*

Department of Computer Science
National Tsing Hua University
Hsinchu 300, Taiwan
E-mail: {bertha, wanchen, peggy, wshih}
+Department of Electrical Engineering and Computer Science
Northwestern University
Evanston 60208, U.S.A.

This paper investigates the problem of testing whether a set of code words satisfies certain biologically motivated Hamming distance constraints. The paper provides three efficient techniques to verify the code words, namely, the Enumeration, Table Lookup, and Encoding methods, with applications to the design of DNA words. The Enumeration method enumerates all combinations of positions in a word, so that all the words in a set can be compared simultaneously and the testing process is improved. The Table Lookup method constructs a data table and divide each word into sub-words to reduce the time complexity of the testing process. The Encoding method which is similar to Table Lookup method uses a linked list to store necessary information in addition. The proposed methods run in O(n) - O(log log n) times faster than the naive method when l = O(log n), where n is the number of code words in a set and l is the length of a word.

Keywords: DNA verification, DNA word design, code word verification, distance constraint, testing algorithm

Full Text () Retrieve PDF document (201003_01.pdf)

Received March 31, 2008; revised May 9, 2008; accepted May 15, 2008.
Communicated by Tsan-sheng Hsu.
* A part of the paper has been presented in National Computer Symposium, NCS Dec. 2007, Asia University, Taichung, Taiwan. The conference is sponsored by Asia University, National Science Council, Institute of Information Science of Academia Sinica, ..., etc.