تحويل بوروز-ويلر

الموسوعة الحرة

تقوم خوارزمية بوروز -ويلر ( BWT ) بإعادة ترتيب سلسلة الأحرف إلى مجموعات من الأحرف المتشابهة، بطريقة يمكن عكسها لاستعادة السلسلة الأصلية. ولأن تقنيات الضغط مثل نقل الأحرف إلى المقدمة وتشفير طول السلسلة تكون أكثر فعالية عند وجود هذه المجموعات، يمكن استخدام خوارزمية بوروز-ويلر كخطوة تمهيدية لتحسين كفاءة خوارزمية الضغط، ويُستخدم هذا الأسلوب في برامج مثل bzip2 . ويمكن تنفيذ الخوارزمية بكفاءة باستخدام مصفوفة اللواحق، ما يؤدي إلى الوصول إلى تعقيد زمني خطي.

ابتكرها ديفيد ويلر عام 1983، ونشرها لاحقًا هو ومايكل بوروز عام 1994. تضمنت ورقتهم البحثية خوارزمية ضغط تُسمى خوارزمية ضغط البيانات بدون فقدان باستخدام فرز الكتل أو BSLDCA ، والتي تضغط البيانات باستخدام تحويل بلوك-ويتني متبوعًا بترميز النقل إلى المقدمة وترميز هوفمان أو الترميز الحسابي . [ 1 ] [ 2 ]

وصف

يتم إجراء التحويل عن طريق إنشاء مصفوفة (تُعرف باسم مصفوفة Burrows-Wheeler [ 3 ] ) التي تكون صفوفها عبارة عن إزاحات دائرية للنص المدخل، مرتبة حسب الترتيب المعجمي ، ثم أخذ العمود الأخير من تلك المصفوفة.

للسماح بعكس عملية التحويل، يلزم اتخاذ خطوة إضافية: إما إعادة فهرس السلسلة الأصلية في مصفوفة بوروز-ويلر مع السلسلة المُحوَّلة (النهج الموضح في الورقة الأصلية لبوروز وويلر [ 1 ] )، أو إضافة حرف خاص في نهاية النص في بداية أو نهاية النص المُدخل قبل تنفيذ التحويل. [ 3 ]

مثال

بفرض وجود سلسلة إدخال (الخطوة 1 في الجدول أدناه)، يتم تدويرها N مرة (الخطوة 2)، حيث يمثل طول السلسلة مع الأخذ في الاعتبار الحرف الأحمر الذي يمثل بداية السلسلة والحرف الأحمر الذي يمثل مؤشر نهاية الملف . ثم يتم فرز هذه التدويرات، أو الإزاحات الدائرية، ترتيبًا معجميًا (الخطوة 3). يكون ناتج مرحلة التشفير هو العمود الأخير بعد الخطوة 3، وفهرس (يبدأ من الصفر) الصف الذي يحتوي على السلسلة الأصلية ، وهو في هذه الحالة .S = ^BANANA$  N = 8S^$ L = BNN^AA$A ISI = 6

ليس من الضروري استخدام كليهما $، ^ولكن يجب استخدام واحد على الأقل، وإلا فلن نتمكن من عكس التحويل، لأن جميع التبديلات الدائرية لسلسلة لها نفس تحويل Burrows-Wheeler.

تحويل
1. الإدخال2. جميع الدورات3. فرز حسب الترتيب المعجمي4. خذ العمود الأخير5. المخرجات
^ موزة $
^ موز $ $ ^ موز موز $ ^​ NA $ ^ BANA ANA $ ^ BAN نانا $ ^ با أنانا $ ^ ب موز $ ^
A NANA $ ^ B A NA $ ^ BAN A $ ^ BANAN B ANANA $ ^ N ANA $ ^ BA N A $ ^ BANA ^ BANANA $ $^ موز
أنانا $ ^ B ANA $ ^ BA N A $ ^ BANA N BANANA $ ^ NANA $ ^ B A NA $ ^ BAN A ^ BANANA $ $^ BANAN A
BNN ^ AA $ A

الشفرة الزائفة

تُقدّم الشفرة الزائفة التالية طريقةً بسيطة (وإن كانت غير فعّالة) لحساب BWT ومعكوسه. وتفترض هذه الشفرة أن سلسلة الإدخال sتحتوي على حرف خاص "EOF"، وهو الحرف الأخير ولا يظهر في أي مكان آخر في النص.

دالة BWT ( سلسلة نصية s) أنشئ جدولًا، حيث تمثل الصفوف جميع عمليات الدوران الممكنة لـ s فرز الصفوف أبجديًا أعد (العمود الأخير من الجدول)
دالة inverseBWT ( سلسلة نصية s) إنشاء جدول فارغ عدد مرات التكرار // أول عملية إدراج تُنشئ العمود الأول أدرج s كعمود في الجدول قبل العمود الأول من الجدول رتب صفوف الجدول أبجديًا أعد (الصف الذي ينتهي بحرف "EOF")

توضيح

إذا احتوت السلسلة الأصلية على عدة سلاسل فرعية تتكرر بكثرة، فإن السلسلة المُحوَّلة باستخدام BWT ستحتوي على عدة مواضع يتكرر فيها حرف واحد عدة مرات متتالية، [ 4 ] مما يُسهِّل ضغط البيانات. على سبيل المثال، لنفترض تحويل نص إنجليزي يحتوي على كلمة "the" بشكل متكرر:

على سبيل المثال:

مدخلTHE.MAN.AND.THE.DOG.WAITED.AT.THE.STATION.FOR.THE.TRAIN.TO.THE.CITY
الناتجNDEENEEODTRNEGRWM..T.EN.HHHHHT.OTTTTTATAC.AOIATDIFOT.ASI..Y..A..I.T

يؤدي فرز دورانات هذا النص إلى تجميع الدورانات التي تبدأ بـ "he" معًا، وعادةً ما يكون الحرف الأخير من هذا الدوران (وهو أيضًا الحرف الذي يسبق "he") هو "t" (مع أنه قد لا يكون كذلك في بعض الأحيان، كما لو كان النص يحتوي على "ache")، لذا ستحتوي نتيجة التحويل على سلسلة، أو سلاسل، من العديد من أحرف "t" المتتالية. وبالمثل، يتم تجميع الدورانات التي تبدأ بـ "e" معًا، ولكن غالبًا ما يسبق "e" الحرف "h"، لذلك نرى أن الناتج أعلاه يحتوي على سلسلة من خمسة أحرف "h" متتالية.

وهكذا يمكن ملاحظة أن نجاح هذا التحويل يعتمد على قيمة واحدة ذات احتمالية عالية للظهور قبل التسلسل، لذلك فهو يحتاج بشكل عام إلى عينات طويلة إلى حد ما (بضعة كيلوبايتات على الأقل) من البيانات المناسبة (مثل النص).

الشيء المميز في BWT ليس أنه يولد مخرجات يسهل ترميزها - فالفرز العادي سيفعل ذلك - ولكن أنه يفعل ذلك بشكل عكسي ، مما يسمح بإعادة إنشاء المستند الأصلي من بيانات العمود الأخير.

يمكن فهم العملية العكسية على النحو التالي: خذ الجدول النهائي في خوارزمية BWT، واحذف جميع الأعمدة باستثناء العمود الأخير. باستخدام هذه المعلومات فقط، يمكنك بسهولة إعادة بناء العمود الأول. يُظهر لك العمود الأخير جميع الأحرف في النص، لذا ما عليك سوى ترتيب هذه الأحرف أبجديًا للحصول على العمود الأول. بعد ذلك، يُعطيك العمودان الأخير والأول (من كل صف) معًا جميع أزواج الأحرف المتتالية في المستند، حيث تُؤخذ الأزواج بشكل دوري بحيث يُشكل الحرف الأخير والأول زوجًا. يُعطيك ترتيب قائمة الأزواج العمودين الأول والثاني . للحصول على العمود الثالث، يُضاف العمود الأخير مرة أخرى إلى بداية الجدول، ويتم ترتيب الصفوف معجميًا. بالاستمرار بهذه الطريقة، يمكنك إعادة بناء القائمة بأكملها. بعد ذلك، يكون الصف الذي يحتوي على حرف "نهاية الملف" في النهاية هو النص الأصلي. يتم عكس المثال أعلاه على النحو التالي:

التحويل العكسي
مدخل
BNN ^ AA $ A
أضف 1الفرز 1أضف 2الفرز 2
ب شمال شمال ^ أ أ أ ​
أ أ أ ب شمال شمال ^ $
بكالوريوس غير متوفر غير متوفر ^ ب AN AN $ ^ A $
AN AN دولار أمريكي بكالوريوس غير متوفر غير متوفر ^ ب $ ^
أضف 3الفرز 3أضف 4فرز 4
حظر نان غير متوفر $ ^ BA أنا أنا $ ^ ب أ $ ^
أنا أنا أ $ ^ حظر نان غير متوفر $ ^ BA $ ^ B
موز نانا غير متاح $ ^ ^ حظر أنان ANA $ $ ^ BA أ $ ^ ب
أنان ANA $ A $ ^ B موز نانا غير متاح $ ^ ^ حظر $ ^ با
أضف 5الفرز 5أضف 6الفرز 6
موز نانا $ نا $ ^ ب ^ بانا أنانا ANA $ ^ $ ^ BAN أ $ ^ با
أنانا ANA $ ^ A $ ^ BA موز نانا $ نا $ ^ ب ^ بانا $ ^ بان
موز نانا $ ^ نا $ ^ با ^ موز أنانا $ أنا $ ^ ب $ ^ بانا حظر $​​
أنانا $ أنا $ ^ ب حظر $​​ موز نانا $ ^ NA $ ^ BA ^ BANAN $ ^ BANA
أضف 7فرز 7أضف 8فرز 8
موز $ نانا $ ^ ب غير متاح $ ^ حظر ^ موز أنانا $ ^ أنا $ ^ با $ ^ بانان أ $ ^ بانا
أنانا $ ^ أنانا $ ^ با أ $ ^ بانا موز $ نانا $ ^ ب غير متوفر $ ^ حظر ^ موز $ ^ موز
موز $ ^ موز $ ^ با NA $ ^ BANA ^ BANANA $ ANANA $ ^ B أنا $ ^ بان $ ^ موز موز $ ^​
أنانا $ ^ ب ANA $ ^ BAN موز $ ^​ موز $ ^ موز $ ^ با NA $ ^ BANA ^ BANANA $ $ ^ BANANA
الناتج
^ موزة $

تحسين

يمكن لعدد من التحسينات أن تجعل هذه الخوارزميات تعمل بكفاءة أكبر دون تغيير المخرجات. لا حاجة لتمثيل الجدول في كل من المُشفِّر والمُفكِّك. في المُشفِّر، يُمكن تمثيل كل صف من الجدول بمؤشر واحد إلى السلاسل النصية، ويتم الفرز باستخدام هذه المؤشرات. في المُفكِّك، لا حاجة أيضًا لتخزين الجدول، ويمكن توليد السلسلة النصية المُفكَّكة حرفًا حرفًا من اليسار إلى اليمين. بل يُمكن الاستغناء عن الفرز المقارن لصالح الفرز الخطي، حيث يتناسب الأداء طرديًا مع حجم الأبجدية وطول السلسلة النصية. يُمكن أن يكون "الحرف" في الخوارزمية بايتًا، أو بتًا، أو أي حجم مناسب آخر.

يمكن أيضًا ملاحظة أنه رياضيًا، يمكن حساب السلسلة المشفرة كتعديل بسيط لمصفوفة اللواحق ، ويمكن حساب مصفوفات اللواحق بزمن وذاكرة خطيين. يمكن تعريف BWT بالنسبة لمصفوفة اللواحق SA للنص T على النحو التالي (فهرسة تبدأ من 1):

بدبليوتي[أنا]={تي[Sأ[أنا]-1]،لو Sأ[أنا]>0دولار،خلاف ذلك{\displaystyle BWT[i]={\begin{cases}T[SA[i]-1],&{\text{إذا كان }}SA[i]>0\\\$,&{\text{فيما عدا ذلك}}\end{cases}}}[ 5 ]

لا حاجة لوجود رمز "نهاية الملف" فعليًا. بدلًا من ذلك، يمكن استخدام مؤشر يُخزّن موقع رمز "نهاية الملف" في السلسلة النصية لو كان موجودًا. في هذه الطريقة، يجب أن يتضمن ناتج تحويل BWT كلًا من السلسلة النصية المُحوّلة والقيمة النهائية للمؤشر. ثم يُعيد التحويل العكسي السلسلة النصية إلى حجمها الأصلي: إذ يُعطى سلسلة نصية ومؤشرًا، ويُعيد سلسلة نصية فقط.

يمكن الاطلاع على وصف كامل للخوارزميات في ورقة بوروز وويلر، أو في عدد من المصادر الإلكترونية. [ 1 ] تختلف الخوارزميات نوعًا ما بحسب استخدام مؤشر نهاية الملف (EOF) واتجاه الفرز. في الواقع، لم تستخدم الصيغة الأصلية مؤشر نهاية الملف. [ 6 ]

صيغة تقابلية

بما أن أي تدوير لسلسلة الإدخال سيؤدي إلى نفس السلسلة المُحوَّلة، فلا يمكن عكس تحويل BWT دون إضافة علامة نهاية الملف (EOF) إلى نهاية الإدخال أو القيام بما يُماثلها، مما يُتيح تمييز سلسلة الإدخال عن جميع تدويراتها. زيادة حجم الأبجدية (عن طريق إضافة حرف نهاية الملف) يجعل خطوات الضغط اللاحقة مُعقدة.

يوجد شكل تقابلي للتحويل، حيث تُعرّف السلسلة المُحوّلة السلسلة الأصلية بشكل فريد، وتكون السلسلتان متساويتين في الطول وتحتويان على نفس الأحرف تمامًا، ولكن بترتيب مختلف. [ 7 ] [ 8 ]

يُحسب التحويل التقابلي بتحليل المدخلات إلى سلسلة غير متزايدة من كلمات ليندون ؛ هذا التحليل موجود وفريد ​​وفقًا لنظرية تشين-فوكس-ليندون [ 9 ] ، ويمكن إيجاده في زمن خطي ومساحة ثابتة [ 10 ] . تُرتّب الخوارزمية دوران جميع الكلمات؛ وكما هو الحال في تحويل بوروز-ويلر، ينتج عن ذلك سلسلة مُرتّبة من n سلسلة نصية. ثم تُستخرج السلسلة المُحوّلة باختيار الحرف الأخير من كل سلسلة في هذه القائمة المُرتّبة. التحذير المهم هنا هو أن السلاسل ذات الأطوال المختلفة لا تُرتّب بالطريقة المعتادة؛ إذ تتكرر السلسلتان إلى ما لا نهاية، وتُرتّب التكرارات اللانهائية. على سبيل المثال، تسبق "ORO" سلسلة "OR" لأن "OROORO..." تسبق "OROROR...".

على سبيل المثال، يتم تحويل النص " ^ BANANA $ " إلى "ANNBAA ^ $ " عبر هذه الخطوات ( يشير الرمز $ الأحمر إلى مؤشر نهاية الملف ) في السلسلة الأصلية. لا حاجة لرمز نهاية الملف في التحويل التقابلي، لذا يتم حذفه أثناء التحويل ثم إضافته مرة أخرى إلى مكانه الصحيح في الملف.

يتم تقسيم السلسلة إلى كلمات ليندون بحيث تتناقص الكلمات في التسلسل باستخدام طريقة المقارنة المذكورة أعلاه. (لاحظ أننا نرتب ' ^ ' كأحرف تالية للأحرف الأخرى). تصبح " ^ BANANA" كالتالي: ( ^ ) (B) (AN) (AN) (A).

التحويل التقابلي
مدخلجميع الدوراتمرتبة أبجديًاالعمود الأخير من كلمة ليندون المدورةالناتج
^ موزة $
^ ^ ^ ^ ^ ^ ^ ^ ... ( ^ )  ب ب ب ب ب ب ب ب ب ... ( ب  ) عنان عنان ... (ان)  نانا نانا ... (غ) عنان عنان... (ان)  نانا نانا... (غ  ) ااااااااااااا ... (أ)
أاااااااااااا ... (أ) أ نانانان... (أن) أ نانانان... (أن) ب ب ب ب ب ب ب... (ب) ن أنانانا... (نا) ن أنانانا... (غ) ^ ^ ^ ^ ^ ^ ^ ^ ... ( ^ )
أ AAAAAAA... ( أ ) A N ANANAN... (A N ) انانانا ...(ا ن ) ب ب ب ب ب ب ب... ( ب ) نانانانا ... ( نانا ) ن ا نانانا... (ن ا ) ^ ^ ^ ^ ^ ^ ^ ^ ... ( ^ )
ANNBAA ^ $
التحويل التقابلي العكسي
مدخل
ANNBAA ^
أضف 1الفرز 1أضف 2الفرز 2
أ شمال شمال ب أ أ ^
أ أ أ ب شمال شمال ^
AA غير متوفر غير متوفر بي بي AN AN ^ ^
AA AN AN بي بي غير متوفر غير متوفر ^ ^
أضف 3الفرز 3أضف 4فرز 4
AAA نان نان مكتب الأعمال الأفضل (BBB) أنا أنا ^ ^ ^
AAA أنا أنا مكتب الأعمال الأفضل (BBB) نان نان ^ ^ ^
AAAA نانا نانا BBBB أنان أنان ^ ^ ^ ^
AAAA أنان أنان BBBB نانا نانا ^ ^ ^ ^
الناتج
^ موز

حتى الخطوة الأخيرة، تكون العملية مطابقة لعملية بوروز-ويلر العكسية، ولكنها هنا لا تُنتج بالضرورة دورات لتسلسل واحد؛ بل تُنتج دورات لكلمات ليندون (التي ستبدأ بالتكرار مع استمرار العملية). هنا، نرى تكرارات لأربع كلمات ليندون مميزة: (أ)، (أن) (مرتين)، (ب)، و(^) . (لا تُمثل NANA كلمة مميزة، لأنها دورة من ANAN...). عند هذه النقطة، تُرتّب هذه الكلمات بترتيب عكسي: ( ^ )، (ب)، (أن)، (أن)، (أ). ثم تُدمج هذه الكلمات للحصول على

^ موز

يمكن اعتبار تحويل بوروز-ويلر حالة خاصة من هذا التحويل التقابلي؛ فبدلاً من إدخال حرف جديد من خارج الأبجدية للدلالة على نهاية السلسلة، يمكننا إدخال حرف جديد يسبق جميع الأحرف الموجودة، ويُوضع في بداية السلسلة. تصبح السلسلة بأكملها كلمة ليندون، وبالتالي فإن تطبيق التحويل التقابلي عليها سينتج عنه تحويل، وعند عكسه، يُعيد كلمة ليندون، دون الحاجة إلى إعادة تجميعها في النهاية.

على سبيل المثال، تطبيق التحويل التقابلي يعطي:

مدخلSIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
كلمات ليندونSIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
الناتجSTEYDST.E.IXXIIXXSMPPXS.B..EE..SUSFXDIOIIIIT

يتضمن التحويل التقابلي ثمانية سلاسل من الأحرف المتطابقة. وهذه السلاسل هي، بالترتيب: XX، II، XX، PP، ..، EE، ..، و IIII.

إجمالاً، تم استخدام 18 حرفاً في هذه الجولات.

تحويل بوروز-ويلر الديناميكي

عند تعديل نص ما، يتغير تحويل بوروز-ويلر الخاص به. يقترح سالسون وآخرون [ 11 ] خوارزمية تستنتج تحويل بوروز-ويلر لنص مُعدَّل من تحويل بوروز-ويلر للنص الأصلي، وذلك بإجراء عدد محدود من عمليات إعادة الترتيب الموضعية في تحويل بوروز-ويلر الأصلي، مما قد يكون أسرع من إنشاء تحويل بوروز-ويلر للنص المُعدَّل مباشرةً.

نموذج للتنفيذ

تُضحّي هذه النسخة المكتوبة بلغة بايثون بالسرعة من أجل البساطة: البرنامج قصير، لكنه يستغرق وقتًا أطول من الوقت الخطي المطلوب في التطبيق العملي. وهو في الأساس يقوم بما يقوم به قسم الشفرة الزائفة.

باستخدام رموز التحكم STX/ETX لتحديد بداية ونهاية النص، وباستخدامها s[i:] + s[:i]لإنشاء iالدوران رقم 1 من s، يأخذ التحويل الأمامي الحرف الأخير من كل صف من الصفوف المصنفة:

from curses.ascii import STX , ETXdef bwt ( s : str , start = chr ( STX ), end = chr ( ETX )) -> str : r """  تطبيق تحويل Burrows-Wheeler على سلسلة الإدخال. >>> bwt('BANANA')  '\x03ANNB\x02AA'  >>> bwt('BANANA', start='^', end='$')  'ANNB^AA$'  >>> bwt('BANANA', start='%', end='$')  'A$NNB%AA'  """ assert ( start not in s and end not in s ), "لا يمكن أن تحتوي سلسلة الإدخال على أحرف STX و ETX" s = f " { start }{ s }{ end } " # إضافة علامة بداية ونهاية النص# جدول دوران السلسلة table = sorted ( f " { s [ i :] }{ s [: i ] } " for i , c in enumerate ( s )) last_column = [ row [ -1 : ] for row in table ] # الأحرف الأخيرة من كل صف return "" . join ( last_column ) # تحويل قائمة الأحرف إلى سلسلة نصية

تقوم عملية التحويل العكسي بإدراج البيانات بشكل متكرر rكعمود أيسر في الجدول، ثم تقوم بفرز الجدول. بعد اكتمال بناء الجدول، تُعيد العملية الصف الذي ينتهي بـ ETX، باستثناء STX و ETX.

def inverse_bwt ( r : str , start = chr ( STX ), end = chr ( ETX )) -> str : r """  تطبيق تحويل Burrows–Wheeler العكسي. >>> inverse_bwt('\x03ANNB\x02AA')  'BANANA'  >>> inverse_bwt('ANNB^AA$', start='^', end='$')  'BANANA'  >>> inverse_bwt('A$NNB%AA', start='%', end='$')  'BANANA'  """ str_len = len ( r ) table = [ "" ] * str_len # إنشاء جدول فارغ for _ in range ( str_len ): table = sorted ( rc + tc for rc , tc in zip ( r , table )) # إضافة عمود من r# تكرار العملية والتحقق مما إذا كان الحرف الأخير ينتهي بـ ETX أم لا s = next ( ( row for row in table if row.endswith ( end ) ), "" )# استرجاع البيانات من المصفوفة وإزالة علامات البداية والنهاية return s . rstrip ( end ) . strip ( start )

استنادًا إلى ملاحظات مانزيني حول التنفيذ، يُمكن استخدام لاحقة فارغة بسيطة بدلاً من ذلك. يجب أن يتم الفرز وفقًا للترتيب المعجمي (قراءة السلسلة من اليمين إلى اليسار)، أي في بايثون. [ 6 ] (في الواقع، لا تُحقق رموز التحكم المذكورة أعلاه شرط أن يكون الحرف الأخير هو نهاية الملف؛ فالرمزان هما في الواقع الحرف الأول . ومع ذلك، يبقى التدوير صحيحًا.)sorted(...,key=lambdas:s[::-1])

تطبيقات BWT

باعتبارها خوارزمية ضغط غير ضائعة، توفر تحويلة بوروز-ويلر ميزة هامة تتمثل في إمكانية عكس عملية التشفير، وبالتالي استعادة البيانات الأصلية من عملية الضغط الناتجة. وقد ساهمت هذه الميزة في تطوير العديد من الخوارزميات لأغراض مختلفة، منها على سبيل المثال لا الحصر، خوارزميات محاذاة التسلسلات ، وضغط الصور ، وضغط البيانات ، وغيرها. فيما يلي عرض لبعض استخدامات تحويلة بوروز-ويلر.

BWT لمحاذاة التسلسل

أدى ظهور تقنيات التسلسل الجيني من الجيل التالي (NGS) في نهاية العقد الأول من الألفية الثانية إلى تطبيق آخر لتحويل بوروز-ويلر. في هذه التقنية، يُجزأ الحمض النووي إلى أجزاء صغيرة، تُسلسل قواعدها القليلة الأولى ، مما ينتج عنه ملايين القراءات، يتراوح طول كل منها بين 30 و500 زوج قاعدي (أحرف الحمض النووي). في العديد من التجارب، مثل ChIP-Seq ، تتمثل المهمة الآن في محاذاة هذه القراءات مع جينوم مرجعي ، أي مع التسلسل المعروف شبه الكامل للكائن الحي قيد الدراسة (والذي قد يصل طوله إلى مليارات الأزواج القاعدية). وقد نُشر عدد من برامج المحاذاة المتخصصة لهذه المهمة، والتي اعتمدت في البداية على التجزئة (مثل Eland وSOAP [ 12 ] وMAQ [ 13 ] ). في محاولة لتقليل متطلبات الذاكرة لمحاذاة التسلسل، تم تطوير العديد من برامج المحاذاة ( Bowtie ، [ 14 ] BWA، [ 15 ] وSOAP2 [ 16 ] ) التي تستخدم تحويل Burrows-Wheeler.

BWT لضغط الصور

أثبتت تحويلة بوروز-ويلر أهميتها الأساسية في تطبيقات ضغط الصور . فعلى سبيل المثال، عرضت الدراسة [ 17 ] مسار ضغط يعتمد على تطبيق تحويلة بوروز-ويلر متبوعًا بالانعكاس، وطول التشغيل، ومشفرات حسابية. يُعرف المسار المُطور في هذه الحالة باسم تحويلة بوروز-ويلر مع مشفر انعكاس (BWIC). وقد أظهرت نتائج BWIC تفوقًا في أداء الضغط لخوارزميات معروفة وشائعة الاستخدام مثل Lossless JPEG و JPEG 2000. كما تفوقت BWIC عليها من حيث حجم الضغط النهائي لصور الأشعة الطبية بنسبة 5.1% و4.1% على التوالي. وقد تحققت هذه التحسينات من خلال دمج BWIC مع مسح مسبق للصورة بترتيب متعرج رأسي. وفي الآونة الأخيرة، أظهرت دراسات إضافية أن تطبيق تحويلة بوروز-ويلر بالتزامن مع تحويلة النقل إلى الأمام (MTF) المعروفة يحقق ضغطًا شبه كامل للصور. [ 18 ]

BWT لضغط قواعد البيانات الجينومية

قدم كوكس وآخرون [ 19 ] مخططًا لضغط البيانات الجينومية يستخدم خوارزمية BWT في المرحلة الأولى من ضغط العديد من مجموعات البيانات الجينومية، بما في ذلك المعلومات الجينومية البشرية. واقترح بحثهم إمكانية تحسين ضغط BWT بإضافة آلية ضغط ثانية تُسمى "الترميز المماثل للسابق" (SAP)، والتي تستفيد من حقيقة أن اللواحق المكونة من حرفين أو أكثر من الأحرف السابقة قد تكون متطابقة. وباستخدام آلية الضغط BWT-SAP، أظهر كوكس وآخرون أنه في قاعدة البيانات الجينومية ERA015743،  التي يبلغ حجمها 135.5 جيجابايت، يضغط مخطط الضغط BWT-SAP مجموعة البيانات ERA015743 بنسبة 94% تقريبًا، لتصبح 8.2  جيجابايت.

BWT للتنبؤ بالتسلسل

أثبتت خوارزمية بوروز-ويلر (BWT) فعاليتها في التنبؤ بالتسلسلات، وهو مجال شائع في تعلم الآلة ومعالجة اللغات الطبيعية . وقد اقترح كتستاكيس وآخرون [ 20 ] مخططًا للتنبؤ بالتسلسلات يُسمى SuBSeq، يستغل ضغط البيانات غير الفاقد للبيانات في تحويل بوروز-ويلر. يستغل SuBSeq خوارزمية BWT باستخراج فهرس FM ، ثم يُجري سلسلة من العمليات تُسمى البحث العكسي، والبحث الأمامي، وتوسيع الجوار، والحصول على النتائج، وذلك للبحث عن التنبؤات بناءً على لاحقة معينة . بعد ذلك، تُصنف التنبؤات بناءً على وزن، وتُوضع في مصفوفة، حيث يُختار العنصر ذو الوزن الأعلى ليكون هو التنبؤ المُقدم من خوارزمية SuBSeq. وقد أظهرت SuBSeq تفوقًا على أحدث الخوارزميات في التنبؤ بالتسلسلات، سواءً من حيث وقت التدريب أو الدقة.

مراجع

  1. 1 2 3 بوروز، مايكل ؛ ويلر، ديفيد جيه. (10 مايو 1994)، خوارزمية ضغط بيانات بدون فقدان باستخدام فرز الكتل ، التقرير الفني 124، شركة ديجيتال إكويبمنت، مؤرشف من الأصل في 5 يناير 2003
  2. ↑ أرنافوت، ز.؛ ماجليفيراس، س.س. (1997). "فرز الكتل وضغطها". وقائع مؤتمر ضغط البيانات DCC '97. مطبعة جمعية مهندسي الكهرباء والإلكترونيات. ص 181-190 . doi : 10.1109/DCC.1997.582009 . ISBN  978-0-8186-7761-8.
  3. 1 2 لانغميد، بن. "تحويل بوروز-ويلر ومؤشر FM" (ملف PDF) . كلية ويتينغ للهندسة بجامعة جونز هوبكنز . تم الاطلاع عليه بتاريخ 23 أبريل 2025 .
  4. ^ "أدريان موجينيت/سكالا-بوت" . جيثب . تم الاسترجاع في 19 أبريل 2018 .
  5. ↑ سيمبسون، جاريد ت.؛ دوربين، ريتشارد (15 يونيو 2010). "بناء فعال لرسم بياني لسلسلة التجميع باستخدام فهرس FM" . المعلوماتية الحيوية . 26 (12): i367– i373. doi : 10.1093/bioinformatics/btq217 . ISSN 1367-4803 . PMC 2881401. PMID 20529929 .   
  6. 1 2 مانزيني، جيوفاني (18 أغسطس 1999). "تحويل بوروز-ويلر: النظرية والتطبيق" (ملف PDF) . وقائع المؤتمر الدولي الرابع والعشرين للأسس الرياضية لعلوم الحاسوب 1999، MFCS'99، شكلارسكا بوريبا، بولندا، 6-10 سبتمبر 1999. سبرينغر ساينس آند بيزنس ميديا. ISBN 9783540664086تمت أرشفة الملف (PDF) من النسخة الأصلية بتاريخ 2022-10-09.
  7. ↑ جيل، ج.؛ سكوت، د.أ. (2009)، تحويل فرز السلاسل الثنائية (ملف PDF) ، مؤرشف من الملف الأصلي (PDF) بتاريخ 2011-10-08 ، تم استرجاعه بتاريخ 2009-07-09
  8. ↑ كوفليتنر، مانفريد (2009)، "حول المتغيرات التقابلية لتحويل بوروز-ويلر"، في هولوب، يان؛ زداريك، يان (محرران)، مؤتمر براغ لعلم الأوتار ، ص 65-69 ، arXiv : 0908.0239 ، Bibcode : 2009arXiv0908.0239K .
  9. ↑
    • لوثير، م. (1997)، التوافقية على الكلمات ، موسوعة الرياضيات وتطبيقاتها، المجلد  17، بيرين، د.؛ رويتناور، س.؛ بيرستل، ج.؛ بين، ج. إ.؛ بيريلو، ج.؛ فواتا، د.؛ ساكاروفيتش، ج.؛ سيمون، إ.؛ شوتزنبرغر، م. ب.؛ شوفروت، س.؛ كوري، ر.؛ ليندون، روجر؛ روتا، جيان كارلو. مقدمة بقلم روجر ليندون (  الطبعة الثانية)، مطبعة جامعة كامبريدج ، ص  67، ISBN 978-0-521-59924-5، Zbl 0874.20040 
  10. ^ دوفال ، جان بيير (1983)، “تحليل الكلمات على أبجدية مرتبة”، مجلة الخوارزميات ، 4 (4): 363–381 ، دوى : 10.1016 / 0196-6774 (83)90017-2 ، ISSN 0196-6774 ، Zbl 0532.68061  .
  11. ↑ سالسون م، ليكروك ت، ليونارد م، موشار ل (2009). "خوارزمية من أربع مراحل لتحديث تحويل بوروز-ويلر" . علوم الحاسوب النظرية . 410 (43): 4350-4359 . doi : 10.1016/j.tcs.2009.07.016 .
  12. ↑ لي ر وآخرون (2008). "SOAP: برنامج محاذاة النيوكليوتيدات القصيرة" . المعلوماتية الحيوية . 24 (5): 713-714 . doi : 10.1093/bioinformatics/btn025 . PMID 18227114 .  
  13. ↑ لي هـ، روان ج، دوربين ر (19 أغسطس 2008). " رسم خرائط قراءات تسلسل الحمض النووي القصيرة وتحديد المتغيرات باستخدام درجات جودة رسم الخرائط" . أبحاث الجينوم . 18 (11): 1851-1858 . doi : 10.1101/gr.078212.108 . PMC 2577856. PMID 18714091 .  
  14. ↑ لانغميد ب، ترابنيل س، بوب م، سالزبيرغ إس إل (2009). "محاذاة فائقة السرعة وفعالة من حيث الذاكرة لتسلسلات الحمض النووي القصيرة مع الجينوم البشري" . علم الأحياء الجينومي . 10 (3) R25. doi : 10.1186/gb-2009-10-3-r25 . PMC 2690996. PMID 19261174 .  
  15. ↑ لي هـ، دوربين ر (2009). " محاذاة سريعة ودقيقة للقراءات القصيرة باستخدام تحويل بوروز-ويلر" . المعلوماتية الحيوية . 25 (14): 1754-1760 . doi : 10.1093/bioinformatics/btp324 . PMC 2705234. PMID 19451168 .  
  16. ↑ لي ر وآخرون (2009). "SOAP2: أداة فائقة السرعة محسّنة لمحاذاة القراءات القصيرة". المعلوماتية الحيوية . 25 (15): 1966-1967 . doi : 10.1093/bioinformatics/btp336 . PMID 19497933 .  
  17. ↑ كولين ب، أرنافوت ز، كوتش ب (2015). "ضغط الصور الطبية بدون فقدان للبيانات باستخدام تحويل بوروز-ويلر مع مُشفِّر الانعكاس". المؤتمر الدولي السنوي السابع والثلاثون لجمعية مهندسي الكهرباء والإلكترونيات في الهندسة الطبية والبيولوجية (EMBC) . المجلد 2015. الصفحات 2956-2959 . doi : 10.1109/EMBC.2015.7319012 . ISBN   978-1-4244-9271-8PMID 26736912 . S2CID 4460328 .​  
  18. ↑ ديفادوس سي بي، سانكاراغوماتي بي (2019). "ضغط الصور الطبية شبه الخالي من الفقد باستخدام تقنيات ضغط BWT-MTF الكتلية وتقنيات الضغط الكسري الهجين" . الحوسبة العنقودية . 22 : 12929-12937 . doi : 10.1007/s10586-018-1801-3 . S2CID 33687086 . 
  19. ↑ كوكس إيه جيه، باور إم جيه، جاكوبي تي، روزون جي (2012). "ضغط قواعد بيانات التسلسل الجينومي على نطاق واسع باستخدام تحويل بوروز-ويلر". المعلوماتية الحيوية . 28 (11). مطبعة جامعة أكسفورد: 1415-1419 . arXiv : 1205.0192 . doi : 10.1093/bioinformatics/bts173 . PMID 22556365 . 
  20. ↑ كتيستاكيس ر، فورنييه-فيجيه ب، بوغليسي إس جيه، رامان ر (2019). "التنبؤ المتسلسل الموجز القائم على تحويل بواسون-ويتني" . تطبيقات قواعد البيانات وأنظمة الخبراء . سلسلة محاضرات في علوم الحاسوب. المجلد 11707. الصفحات 91-101 . doi : 10.1007/978-3-030-27618-8_7 . ISBN   978-3-030-27617-1. S2CID 201058996 .