THE MATRIX ITERATION ALGORITHM SOLVING AN ENUMERATION PROBLEM ON BACTERIAL COMPLETE GENOMES

Hua Kang YANG;Cheng Xiang HUANG;Xiao Wei WEN

Journal of Systems Science & Complexity ›› 2004, Vol. 14 ›› Issue (2) : 220-236.

PDF(161 KB)
PDF(161 KB)
Journal of Systems Science & Complexity ›› 2004, Vol. 14 ›› Issue (2) : 220-236.
article

THE MATRIX ITERATION ALGORITHM SOLVING AN ENUMERATION PROBLEM ON BACTERIAL COMPLETE GENOMES

  • Hua Kang YANG,Cheng Xiang HUANG,Xiao Wei WEN
Author information +
History +

Abstract

Given an alphabet Σ and a finite minimal set B of forbidden words, a combinatorial enumeration problem on bacterial complete genomes is transformed to enumerating strings of a given length which do not contain any string in B as their substrings. From the fact that a string in the language is equivalent to a path in the corresponding graph, we have obtained a polynomial time algorithm by modifying the power of the adjacency matrix in the graph.

Key words

Bacterial complete genome / alphabet Σ / minimal set B\ of forbidden words / $\widetilde{L^{k}}

Cite this article

Download Citations
Hua Kang YANG , Cheng Xiang HUANG , Xiao Wei WEN. THE MATRIX ITERATION ALGORITHM SOLVING AN ENUMERATION PROBLEM ON BACTERIAL COMPLETE GENOMES. Journal of Systems Science and Complexity, 2004, 14(2): 220-236
PDF(161 KB)

108

Accesses

0

Citation

Detail

Sections
Recommended

/