Handling updates of a biological sequence based on Hidden Markov Models

Changjin Hong, Ahmed H. Tewfik, David H.C. Du

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

The computational complexity of evaluating homologies between a gene sequence and profile Hidden Markov Models (HMMs) is relatively high. Unfortunately, researchers must re-evaluate matches every time they discover an error in a sequence or encounter a mutation of the sequence. Since these occurrences are frequent, it is desirable to have a low complexity procedure for updating the matching result when a small perturbation in a given input gene sequence is observed. In this paper, we describe such a procedure based on a sensitivity analysis of the Viterbi algorithm used to evaluate the similarity of an unknown gene sequence and a profile HMMs. By extending single arc tolerance bounds to the evaluation of the relative change in all nodes' distances from a root node, our algorithm skips all unperturbed parts of a sequence. As a result, our proposed algorithm can update the matching decision in only 20% of the time required by the current approach that computes a new match with the perturbed sequence and base HMM model.

Original languageEnglish (US)
Title of host publication13th European Signal Processing Conference, EUSIPCO 2005
Pages1874-1877
Number of pages4
StatePublished - Dec 1 2005
Event13th European Signal Processing Conference, EUSIPCO 2005 - Antalya, Turkey
Duration: Sep 4 2005Sep 8 2005

Publication series

Name13th European Signal Processing Conference, EUSIPCO 2005

Other

Other13th European Signal Processing Conference, EUSIPCO 2005
CountryTurkey
CityAntalya
Period9/4/059/8/05

Fingerprint Dive into the research topics of 'Handling updates of a biological sequence based on Hidden Markov Models'. Together they form a unique fingerprint.

Cite this