إعادة ترتيب الأشجار

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

• 
  تبادل الجوار الأقرب (NNI)
• 
  تقليم وإعادة تطعيم الأشجار الفرعية (SPR)
• 
  تقسيم الشجرة وإعادة توصيلها (TBR)

أبسط أنواع إعادة ترتيب الأشجار، والمعروفة باسم تبادل أقرب جار ، تُبدّل اتصال أربع أشجار فرعية داخل الشجرة الرئيسية. ولأن هناك ثلاث طرق ممكنة لربط أربع أشجار فرعية، ^{[ 1 ]} إحداها هي الاتصال الأصلي، فإن كل عملية تبادل تُنشئ شجرتين جديدتين. يُعد البحث الشامل عن أقرب الجيران الممكنين لكل مجموعة ممكنة من الأشجار الفرعية أبطأ الطرق، ولكنه الأكثر كفاءة لإجراء هذا البحث. أما البحث البديل، وهو تقليم وإعادة تطعيم الأشجار الفرعية (SPR)، فيُتيح اختيار شجرة فرعية من الشجرة الرئيسية وإزالتها، ثم إعادة إدخالها في مكان آخر على الشجرة الرئيسية لإنشاء عقدة جديدة. وأخيرًا، يقوم تقسيم الشجرة وإعادة توصيلها (TBR) بفصل شجرة فرعية عن الشجرة الرئيسية عند عقدة داخلية، ثم يُحاول إنشاء جميع الاتصالات الممكنة بين حواف الشجرتين الناتجتين. يرتبط ازدياد تعقيد تقنية إعادة ترتيب الأشجار بزيادة الوقت الحسابي المطلوب للبحث، وإن لم يكن بالضرورة بأدائها. ^{[ 2 ]}

يمكن تقسيم SPR إلى نوعين: uSPR (SPR غير الجذري) و rSPR (SPR الجذري). يُطبق uSPR على الأشجار غير الجذرية، ويعمل كالتالي: يتم قطع أي حافة، ثم يتم توصيل أحد طرفي الحافة (المختار عشوائيًا) بأي حافة أخرى في الشجرة. أما rSPR فيُطبق على الأشجار الجذرية*، ويعمل كالتالي: يتم قطع أي حافة باستثناء الحافة المؤدية إلى العقدة الجذرية، ثم يتم توصيل أحد طرفي الحافة (وتحديدًا: الطرف الأبعد عن الجذر) بأي حافة أخرى في الشجرة. ^{[ 3 ]}

* في هذا المثال، يتم تمييز جذر الشجرة بعقدة من الدرجة الأولى، مما يعني أن جميع العقد في الشجرة إما من الدرجة 1 أو الدرجة 3. وهناك نهج بديل، مستخدم في بوردويتش وسيمبل، وهو اعتبار العقدة الجذرية من الدرجة 2، وأن يكون هناك قاعدة خاصة لـ rSPR.

يمكن حساب عدد حركات SPR ^{[ 4 ]} أو TBR ^{[ 5 ]} اللازمة للانتقال من شجرة إلى أخرى عن طريق إنشاء غابة اتفاق قصوى تتألف من أشجار جذرية أو غير جذرية (على التوالي). هذه المسألة صعبة الحل من نوع NP، ولكنها قابلة للحل باستخدام المعاملات الثابتة.

يبدأ أبسط أنواع دمج الأشجار بشجرتين تم تحديدهما مسبقًا على أنهما شبه مثاليتين؛ وبالتالي، من المرجح أن تكون غالبية عقدهما صحيحة، لكنهما قد لا تتمكنان من تحديد "أوراق" الشجرة الفردية بشكل صحيح؛ على سبيل المثال، قد لا يكون الفصل ((A,B),(C,D)) عند طرف الفرع واضحًا مقارنةً بـ ((A,C),(B,D)). ^{[ 1 ]} يقوم دمج الأشجار بتبديل هذين الحلين بين شجرتين شبه مثاليتين. تستخدم متغيرات هذه الطريقة خوارزميات جينية قياسية مع دالة هدف محددة لتبديل الأشجار الفرعية ذات الدرجات العالية في الأشجار الرئيسية ذات الدرجات العالية إجمالًا. ^{[ 6 ]}

تتمثل إحدى الاستراتيجيات البديلة في فصل جزء من الشجرة (والذي يمكن اختياره عشوائيًا، أو باستخدام نهج أكثر استراتيجية) وإجراء خوارزميات TBR/SPR/NNI على هذه الشجرة الفرعية. بعد ذلك، يمكن إعادة هذه الشجرة الفرعية المُحسَّنة إلى الشجرة الرئيسية، مما يُحسِّن قيمة p-score. ^{[ 7 ]}

لتجنب الوقوع في الحلول المثلى المحلية، يمكن استخدام أسلوب "التقسية المحاكاة"، حيث يُسمح للخوارزمية أحيانًا بالنظر في أشجار مرشحة دون المستوى الأمثل، باحتمالية مرتبطة بمدى بعدها عن الحل الأمثل. ^{[ 7 ]}

بمجرد جمع مجموعة من الأشجار المثلى بالتساوي، غالباً ما يكون من الممكن إيجاد شجرة أفضل من خلال دمج "الأجزاء الجيدة" من الأشجار المنفصلة. يمكن تبديل المجموعات الفرعية ذات التركيب المتطابق ولكن بطوبولوجيا مختلفة وتقييم الأشجار الناتجة. ^{[ 7 ]}