Testing whether a set of code words satisfies a given set of constraints

Hsin Wen Wei*, Wan Chen Lu, Pei Chi Huang, Wei Kuan Shih, Ming-Yang Kao

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)333-346
Number of pages14
JournalJournal of Information Science and Engineering
Volume26
Issue number2
StatePublished - Mar 1 2010

Fingerprint

Table lookup
Testing
Hamming distance
DNA

Keywords

  • Code word verification
  • Distance constraint
  • Dna verification
  • Dna word design
  • Testing algorithm

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Hardware and Architecture
  • Library and Information Sciences
  • Computational Theory and Mathematics

Cite this

Wei, Hsin Wen ; Lu, Wan Chen ; Huang, Pei Chi ; Shih, Wei Kuan ; Kao, Ming-Yang. / Testing whether a set of code words satisfies a given set of constraints. In: Journal of Information Science and Engineering. 2010 ; Vol. 26, No. 2. pp. 333-346.
@article{39ecaed70c0446eab74c726bef0cb077,
title = "Testing whether a set of code words satisfies a given set of constraints",
abstract = "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 = "Code word verification, Distance constraint, Dna verification, Dna word design, Testing algorithm",
author = "Wei, {Hsin Wen} and Lu, {Wan Chen} and Huang, {Pei Chi} and Shih, {Wei Kuan} and Ming-Yang Kao",
year = "2010",
month = "3",
day = "1",
language = "English (US)",
volume = "26",
pages = "333--346",
journal = "Journal of Information Science and Engineering",
issn = "1016-2364",
publisher = "Institute of Information Science",
number = "2",

}

Testing whether a set of code words satisfies a given set of constraints. / Wei, Hsin Wen; Lu, Wan Chen; Huang, Pei Chi; Shih, Wei Kuan; Kao, Ming-Yang.

In: Journal of Information Science and Engineering, Vol. 26, No. 2, 01.03.2010, p. 333-346.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Testing whether a set of code words satisfies a given set of constraints

AU - Wei, Hsin Wen

AU - Lu, Wan Chen

AU - Huang, Pei Chi

AU - Shih, Wei Kuan

AU - Kao, Ming-Yang

PY - 2010/3/1

Y1 - 2010/3/1

N2 - 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.

AB - 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.

KW - Code word verification

KW - Distance constraint

KW - Dna verification

KW - Dna word design

KW - Testing algorithm

UR - http://www.scopus.com/inward/record.url?scp=77950405104&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77950405104&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:77950405104

VL - 26

SP - 333

EP - 346

JO - Journal of Information Science and Engineering

JF - Journal of Information Science and Engineering

SN - 1016-2364

IS - 2

ER -