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 str...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.展开更多
基金This research is supported by the National Natural Science Foundation of China (No. 10271103) Natural Science Foundation of Yunnan Province(No. 2003F0015M).
文摘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.
