Constrained dynamic programming inference of Markov networks from finite sets of sample strings

The research reported is an extension of work accomplished by others in automated machine inference of structural models from finite sets of sample strings. The extension has focused on modifying a key algorithm, the dynamic programming technique, to make it less costly and to thus make resulting applications more practical.

Two major modifications of the dynamic programming technique have been designed and implemented. In one, an algorithm for eliminating computation of major portions of the dynamic programming cost matrix was implemented. In the other, a set of redundant calculations was identified and eliminated from the cost matrix computation. The code was implemented on several different computer systems. Results reported here were gathered from code implemented in the C programming language under the VMS operating system on a VAX 8750 computer.

Elimination of redundant calculations yielded time speedups of 900% over a previous implementation. Eliminating computation of portions of the cost matrix yielded time improvements of almost 100% but actually cost more time with the code in which the redundant calculations had been eliminated. When using the application to recognize / classify strings drawn from human chromosome data, the partial matrix code yielded an average 96.5% correct classifications ~ an increase over the 94.25% yielded by the full matrix computation code.

The research has provided a more time efficient technique for automated machine inference of structural models using dynamic programming and has shown that object classification using structural models can be improved upon by eliminating from computation portions of the dynamic programming cost matrix.