Expressing a set of strings for genome information and DP matching

Yoshiyuki KOTANI (

Dept. of Computer Science, Tokyo Univ. of Agric. and Tech.


Ordinary DP matching method deals only with simple strings. Here we propose a new algorithm of DP matching, which is extended for regular expression or wild cards, and contains strings of non-deterministic elements. It receives a pair of symbol string expressions, and generates their matching information. It contains calculation of matching weight which indicates matching degree of each pair of symbols, including wild cards. It also generates a new symbol string description for further matching process.