بالنسبة لهذا البحث، نقدم الآلية فيتربي لفك تشفير النماذج المخفية الماركوفي (HMMs) بمساحة أصغر من الخطية. وتشير تحليلنا على HMMs من طورين إلى أن الذاكرة القصوى المتوقعة المستخدمة لفك سلسلة طولها $n$ مع HMM من طور $m$ يمكن أن تكون بحد أدنى من $Theta(mlog n)$، دون تبطئ كبير في مقارنة مع الآلية الفيتربي التقليدية. وتتطلب الآلية الفيتربي التقليدية $O(mn)$ من الذاكرة، والتي هي غير عملية لتحليل السلاسل الحمضية الطويلة (مثل كروموسومات الوحدة البشرية الكاملة) وللسياقات البيانات المستمرة. كما أننا نظهر أداء الآلية فيتربي الآلية على HMM بسيط لإيجاد الجينات على السلاسل الحمضية المصطبة والحقيقية.
تحميل البحث