بهبود كارايي انديس گذاري باروز-ويلر براي هم‏ترازسازي توالي‏هاي خوانش كوتاه با انتخاب زيرمجموعه‏اي از ماتريس پسوند

هم‏ترازسازي توالي‏ها يكي از وظايف مهم در بيوانفورماتيك است. الگوريتم‏هاي هم‏ترازسازي توالي‏ها در دو دسته‏ي كلي مبتني بر برنامه نويسي پويا و الگوريتم‏هاي ابتكاري قرار مي‏گيرند. در الگوريتم‏هاي نوع دوم، انديس گذاري ژنوم‏ها يك مرحله‏ي پيش نياز مهم است. تبديل باروز-ويلر يك روش انديس گذاري پركاربرد است كه علاوه بر مصرف حافظه‏ي كم، ساختار مناسبي براي جستجوي سريع و دقيق در توالي‏ها فراهم مي‏كند. اين انديس در سه مرحله ساخته مي‏شود؛ ساختن ماتريس پسوند، مرتب سازي پسوند‏ها و ساختن داده‏هاي كمكي مربوط به انديس. بررسي‏ها نشان مي‏دهد كه مرحله‏ي مرتب سازي پسوند‏ها داراي بيشترين زمان اجرا است بطوريكه براي يك توالي به طول 25600 نماد، بيش از 3 ساعت طول مي‏كشد. در اين مقاله يك روش براي بهبود زمان انديس گذاري باروز-ويلر با استفاده از تغييري كوچك در مرتب سازي ماتريس پسوند‏ها معرفي شده كه بر اساس ويژگي‏هاي الگوريتم جستجوي دقيق عقبگرد پيشنهاد شده است. اين الگوريتم جستجو يكي از الگوريتم‏هاي ابزار هم‏ترازسازي باروز-ويلر است كه براي جستجوي توالي‏هاي خوانش كوتاه توليد شده توسط فناوري‏هاي تعيين توالي جديد (حداكثر 100 نماد)، در ژنوم‏ها به كار مي‏رود. ايده‏ي اصلي، كاهش اندازه‏ي مسئله‏ي مرتب سازي با انتخاب پيشوندي از تمام سطر‏هاي ماتريس پسوند بر اساس نياز‏هاي الگوريتم جستجوي دقيق عقبگرد است؛ به طوريكه، در درستي الگوريتم جستجو تأثير منفي نداشته باشد. نتايج حاصل از اجراي الگوريتم نشان مي‏دهد كه با انتخاب طول 100 براي پيشوند‏ها، زمان انديس گذاري يك توالي 25600 نمادي از حدود 4/3 ساعت به 5/3 دقيقه كاهش مي‏يابد. با توجه به اينكه فناوري‏هاي تعيين توالي جديد، خوانش‏هايي با طول كوتاه توليد مي‏كنند، مي‏توان با انتخاب طول پيشوند متناسب با اين فناوري‏ها، روش پيشنهادي را بدون از دست دادن درستي الگوريتم جستجو به كار برد.