Fast Solutions for DNA Code Words Test

• Autorzy: Oprocha P.
• Języki publikacji: EN

Abstrakty

EN

An essential part of any DNA computation is to encode data on DNA strands. Performing such computation we must be sure that no undesirable hybridization will occur. The aim of this paper is to present algorithms which can test if a given set of code words satisfies certain coding and involutory properties, as it is necessary to prevent undesirable DNA strands interactions. These algorithms are based on the theory of codes and pattern matching methods. If we denote by m sum of the lengths of words in a given set, then all presented algorithms can be realized with O(m2) complexity both for time and space.

Słowa kluczowe

EN

DNA; strings properties; code; complexity; algorithms

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2006
• Tom: Vol. 15
• Strony: 41--53
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Oprocha P.

• AGH University of Science and Technology, Faculty of Applied Mathematics Al. Mickiewicza 39, 30-059 Kraków, Poland, and Jagiellonian University, Institute of Mathematics Reymonta 4, 30-059 Kraków, Poland,

Bibliografia

• [1] Aho A.V., Hopcroft J.E., Ullman J.D.; The Design and Analysis of Computer Algorithms, Addison Wesley, 1974.
• [2] Bertsel J., Perrin D.; Theory of Codes, Academic Press, Inc. Orlando Florida,1985.
• [3] Cormen T.H., Leiserson C.E., Rivest R.L.; Introduction to Algorithms, Cambridge 1991.
• [4] Crochemore M., Rytter W.; Text Algorithms, Oxford University Press, 1994.
• [5] Gusfield D.; Algorithms on Strings, Trees and Sequences, Cambridge 1997.
• [6] Jonoska N., Mahalingham K.; Languages of DNA based code words, in: J. Chien,J. Reif, (eds.), Preliminary Proceedings of the 9th International Meeting on DNA Based Computers, 2003, pp. 58-68.53
• [7] Jonoska N., Kephart D.E., Mahalingam K.; Generating DNA Code Words, Congressus Numerantium, 156, 2002, pp. 99-110.
• [8] Jonoska N.; Trends in Computing with DNA, J. Comput. Sci. Technol., 19, 2004.
• [9] Kari L., Konstantinidis S., Losseva E., Wozniak G.; Sticky free and overhang free DNA languages, Acta Informatica, 40(2), 2003, pp. 119-157.
• [10] Kephart D.E., LeFevre J.; CODEGEN: The Generation and Testing of DNA Code Words, to appear in IEEE. Received September 30, 2004