خوارزمية نيدلمان-وونش

خوارزمية نيدلمان -وونش هي خوارزمية تُستخدم في المعلوماتية الحيوية لمحاذاة تسلسلات البروتينات أو النيوكليوتيدات . كانت من أوائل تطبيقات البرمجة الديناميكية لمقارنة التسلسلات البيولوجية. طُوّرت الخوارزمية على يد سول ب. نيدلمان وكريستيان د. وونش ونُشرت عام ١٩٧٠. ^[١]^تقوم الخوارزمية ^أساسًا بتقسيم المشكلة الكبيرة (مثل التسلسل الكامل) إلى سلسلة من المشكلات الأصغر، وتستخدم حلول هذه المشكلات الأصغر لإيجاد الحل الأمثل للمشكلة الأكبر. ^[^٢^] يُشار إليها أحيانًا بخوارزمية المطابقة المثلى وتقنية المحاذاة الشاملة . لا تزال خوارزمية نيدلمان-وونش تُستخدم على نطاق واسع للمحاذاة الشاملة المثلى، خاصةً عندما تكون جودة المحاذاة الشاملة في غاية الأهمية. تُعيّن الخوارزمية درجة لكل محاذاة ممكنة، والغرض منها هو إيجاد جميع المحاذاة الممكنة التي تحمل أعلى درجة.

مقدمة

يمكن استخدام هذه الخوارزمية لأي سلسلتين نصيتين . سيستخدم هذا الدليل سلسلتين صغيرتين من الحمض النووي كمثالين كما هو موضح في الشكل 1:

GCATGCG جاتكا

بناء الشبكة

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

		جي	ج	أ	تي	جي	ج	جي

جي
أ
تي
تي
أ
ج
أ

اختيار نظام التقييم

بعد ذلك، حدد كيفية تقييم كل زوج من الأحرف على حدة. باستخدام المثال أعلاه، قد يكون أحد خيارات المحاذاة المحتملة كما يلي:

12345678 GCATG-CGجي-أتاكا

قد تتطابق الأحرف، أو لا تتطابق، أو تتطابق مع فجوة (حذف أو إدخال ( indel )):

التطابق: الحرفان الموجودان في الفهرس الحالي متطابقان.
عدم تطابق: الحرفان الموجودان في الفهرس الحالي مختلفان.
الإضافة أو الحذف (Indel): أفضل محاذاة تتضمن محاذاة حرف واحد مع فجوة في السلسلة الأخرى.

يُخصَّص لكل سيناريو من هذه السيناريوهات درجة، ومجموع درجات جميع الأزواج هو درجة المرشح الكامل للمحاذاة. توجد أنظمة مختلفة لتخصيص الدرجات؛ وقد تم توضيح بعضها في قسم أنظمة التقييم أدناه. في الوقت الحالي، سيتم استخدام النظام الذي استخدمه نيدلمان وونش ^{[ 1 ] :}

النتيجة: +1
عدم تطابق أو حذف/إضافة: -1

بالنسبة للمثال أعلاه، ستكون نتيجة المحاذاة 0:

GCATG-CGجي-أتاكا +−++−−+− −> 1*4 + (−1)*4 = 0

ملء الجدول

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

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

النتيجة النهائية للخلية هي الأعلى من بين النتائج الثلاث المرشحة.

بما أنه لا توجد خلايا "علوية" أو "علوية يسارية" في الصف الأول، فإنه يمكن استخدام الخلية الموجودة على يسارها فقط لحساب قيمة كل خلية. لذا، يُضاف -1 لكل إزاحة إلى اليمين، لأن ذلك يُمثل حذفًا أو إضافةً من القيمة السابقة. ينتج عن ذلك أن يكون الصف الأول كالتالي: 0، -1، -2، -3، -4، -5، -6، -7. وينطبق الأمر نفسه على العمود الأول، حيث لا يمكن استخدام سوى القيمة الموجودة أعلى كل خلية. وبالتالي، يكون الجدول الناتج كالتالي:

		جي	ج	أ	تي	جي	ج	جي
	0	-1	-2	-3	-4	-5	-6	-7
جي	-1
أ	-2
تي	-3
تي	-4
أ	-5
ج	-6
أ	-7

الحالة الأولى التي تتضمن نتائج في جميع الاتجاهات الثلاثة هي تقاطع الحرفين الأولين (في هذه الحالة G و G). الخلايا المحيطة موضحة أدناه:

		جي
	0	-1
جي	-1	X

تحتوي هذه الخلية على ثلاثة مجاميع مرشحة محتملة:

الجار القطري العلوي الأيسر لديه درجة 0. الزوج G و G متطابق، لذا أضف درجة التطابق: 0 + 1 = 1
الجار العلوي لديه درجة -1، والانتقال من هناك يمثل عملية إدخال/حذف، لذا أضف درجة الإدخال/الحذف: (-1) + (-1) = (-2)
الجار الأيسر لديه أيضًا درجة -1، ويمثل عملية حذف/إدخال، وينتج أيضًا (-2).

أعلى مرشح هو 1 ويتم إدخاله في الخلية:

		جي
	0	-1
جي	-1	1

يجب أيضًا تسجيل الخلية التي أعطت أعلى درجة للمرشح. في الرسم التخطيطي المكتمل في الشكل 1 أعلاه، يُمثَّل ذلك بسهم من الخلية في الصف والعمود 2 إلى الخلية في الصف والعمود 1.

في المثال التالي، تمثل الخطوة القطرية لكل من X و Y عدم تطابق:

		جي	ج
	0	-1	-2
جي	-1	1	X
أ	-2	Y

X:

أعلى: (−2)+(−1) = (−3)
اليسار: (+1)+(−1) = (0)
أعلى اليسار: (−1)+(−1) = (−2)

Y:

أعلى: (1)+(−1) = (0)
اليسار: (−2)+(−1) = (−3)
أعلى اليسار: (−1)+(−1) = (−2)

بالنسبة لكل من X و Y، فإن أعلى درجة هي صفر:

		جي	ج
	0	-1	-2
جي	-1	1	0
أ	-2	0

يمكن تحقيق أعلى درجة للمرشحين من خلال خليتين متجاورتين:

	تي	جي
تي	1	1
أ	0	X

أعلى: (1)+(−1) = (0)
أعلى اليسار: (1)+(−1) = (0)
اليسار: (0)+(−1) = (−1)

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

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

تتبع الأسهم إلى الأصل

ارسم مسارًا من الخلية الموجودة في أسفل اليمين إلى الخلية الموجودة في أعلى اليسار باتباع اتجاه الأسهم. ومن هذا المسار، يتم إنشاء التسلسل وفقًا لهذه القواعد:

يمثل السهم القطري تطابقًا أو عدم تطابق، لذا فإن حرف العمود وحرف صف الخلية الأصلية سيتطابقان.
يمثل السهم الأفقي أو الرأسي عملية إدخال/حذف. تقوم الأسهم الرأسية بمحاذاة الفجوة ("-") مع حرف الصف (تسلسل "الجانب")، بينما تقوم الأسهم الأفقية بمحاذاة الفجوة مع حرف العمود (تسلسل "الأعلى").
إذا وُجدت أسهم متعددة للاختيار من بينها، فإنها تُمثل تفرعات في مسارات المحاذاة. إذا كان فرعان أو أكثر ينتميان إلى مسارات من الخلية السفلية اليمنى إلى الخلية العلوية اليسرى، فإنها تُمثل مسارات محاذاة مُحتملة بنفس القدر. في هذه الحالة، تُعتبر المسارات مُرشحة محاذاة مُنفصلة.

باتباع هذه القواعد، تكون خطوات أحد المرشحين المحتملين للمحاذاة في الشكل 1 كما يلي:

G → CG → GCG → -GCG → T-GCG → AT-GCG → CAT-GCG → GCAT-GCG A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA → G-ATTACA ↓ (فرع) → TGCG → -TGCG → ... → TACA → TTACA → ...

أنظمة التسجيل

مخططات التقييم الأساسية

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

التطابق = 0
إنديل = -1
عدم التطابق = -1

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

التطابق = 1
إنديل = -10
عدم التطابق = -1

مصفوفة التشابه

تُخصّص أنظمة التقييم الأكثر تعقيدًا قيمًا ليس فقط لنوع التغيير، بل أيضًا للأحرف المعنية. على سبيل المثال، قد يُعطى تطابق A وA قيمة 1، بينما قد يُعطى تطابق T وT قيمة 4. هنا (بافتراض نظام التقييم الأول)، تُعطى أهمية أكبر لتطابق T مقارنةً بتطابق A، أي يُفترض أن تطابق T أكثر أهمية للمحاذاة. وينطبق هذا الترجيح القائم على الأحرف أيضًا على حالات عدم التطابق.

لتمثيل جميع التوليفات الممكنة للأحرف ونتائجها، تُستخدم مصفوفة تشابه. وتُمثل مصفوفة التشابه لأبسط نظام كما يلي:

	أ	جي	ج	تي
أ	1	-1	-1	-1
جي	-1	1	-1	-1
ج	-1	-1	1	-1
تي	-1	-1	-1	1

تمثل كل درجة تحولًا من أحد الحروف التي تتطابق معها الخلية إلى الحرف الآخر. وبالتالي، يمثل هذا جميع التطابقات وعدم التطابقات الممكنة (لأبجدية ACGT). لاحظ أن جميع التطابقات تقع على طول القطر، كما أنه ليس من الضروري ملء الجدول بأكمله، بل هذا المثلث فقط لأن الدرجات متبادلة (درجة A → C = درجة C → A). عند تطبيق قاعدة TT = 4 المذكورة أعلاه، يتم إنتاج مصفوفة التشابه التالية:

	أ	جي	ج	تي
أ	1	-1	-1	-1
جي	-1	1	-1	-1
ج	-1	-1	1	-1
تي	-1	-1	-1	4

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

عقوبة الفجوة

عند محاذاة التسلسلات، غالبًا ما توجد فجوات (أي عمليات إدخال/حذف)، وأحيانًا تكون كبيرة. بيولوجيًا، من المرجح أن تحدث الفجوة الكبيرة كحذف واحد كبير بدلًا من عدة عمليات حذف فردية. لذا، يجب أن يكون لعمليتي إدخال/حذف صغيرتين درجة أسوأ من عملية إدخال/حذف كبيرة واحدة. الطريقة البسيطة والشائعة للقيام بذلك هي عبر منح درجة عالية لبداية الفجوة لعملية إدخال/حذف جديدة، ودرجة أقل لتمديد الفجوة لكل حرف يُضيف إلى عملية الإدخال/الحذف. على سبيل المثال، قد تُكلف عملية إدخال/حذف جديدة -5، وقد تُكلف عملية تمديد عملية الإدخال/الحذف -1. وبهذه الطريقة، تكون المحاذاة مثل:

GAAAAAAT G--AAT

والتي تحتوي على عدة محاذاة متساوية، وبعضها يحتوي على عدة محاذاة صغيرة، ستتم محاذاتها الآن على النحو التالي:

GAAAAAAT GAA----T

أو أي محاذاة مع فجوة طويلة 4 بدلاً من فجوات صغيرة متعددة.

عرض متقدم للخوارزمية

تُحدد درجات محاذاة الأحرف بواسطة مصفوفة التشابه . هنا، $S (a, b)$ هي درجة تشابه الحرفين a و b . وتستخدم هذه المصفوفة عقوبة الفجوة الخطية ، والتي تُسمى هنا $d$ .

على سبيل المثال، إذا كانت مصفوفة التشابه

	أ	جي	ج	تي
أ	10	-1	-3	-4
جي	-1	7	-5	-3
ج	-3	-5	9	0
تي	-4	-3	0	8

ثم المحاذاة:

AGACTAGTTAC CGA---GACGT

مع خصم فارق قدره -5، ستكون النتيجة كالتالي:

S (A,C) + S (G,G) + S (A,A) + (3 \times d) + S (G,G) + S (T,A) + S (T,C) + S (A,G) + S (C,T)

= −3 + 7 + 10 − (3 × 5) + 7 + (−4) + 0 + (−1) + 0 = 1

لإيجاد المحاذاة ذات أعلى درجة، يتم تخصيص مصفوفة ثنائية الأبعاد (أو مصفوفة ) F. ويُرمز هنا إلى العنصر الموجود في الصف i والعمود j بـ $F_{ij}$ يوجد صف واحد لكل حرف في التسلسل A ، وعمود واحد لكل حرف في التسلسل B. وبالتالي، عند محاذاة تسلسلات بأحجام n و m ، يكون مقدار الذاكرة المستخدمة هو $O(nm)$ لا تحتفظ خوارزمية هيرشبرغ إلا بمجموعة فرعية من المصفوفة في الذاكرة وتستخدم $\Theta (\min\{n,m\})$ مساحة، ولكنه يشبه إلى حد كبير طريقة نيدلمان-وونش (ولا يزال يتطلب مساحة). $O(nm)$ وقت).

مع تقدم الخوارزمية، $F_{ij}$ سيتم تحديد النتيجة المثلى لمحاذاة الأول $i=0,\dotsc ,n$ الشخصيات في أ والأول $j=0,\dotsc ,m$ الأحرف في B. ثم يتم تطبيق مبدأ الأمثلية على النحو التالي :

أساس:

F_{0j}=d*j

F_{i0}=d*i

الاستدعاء الذاتي، بناءً على مبدأ الأمثلية:

F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),\;F_{i,j-1}+d,\;F_{i-1,j}+d)

وبالتالي، تبدو الشفرة الزائفة للخوارزمية المستخدمة لحساب مصفوفة F على النحو التالي:

د ← نقاط جزاء الفجوة من i = 0 إلى الطول (أ) F(i,0) ← d * i من أجل j = 0 إلى الطول (B) F(0,j) ← d * j for i = 1 to length (A) for j = 1 to length (B) { تطابق ← F(i−1, j−1) + S(A _i , B _j ) احذف ← F(i−1, j) + d أدخل ← F(i, j−1) + d F(i,j) ← max (Match, Insert, Delete) }

بمجرد حساب مصفوفة F ، يكون المدخل $F_{nm}$ يُعطي أعلى درجة بين جميع عمليات المحاذاة الممكنة. لحساب محاذاة تُعطي هذه الدرجة، ابدأ من الخلية السفلية اليمنى، وقارن القيمة مع المصادر الثلاثة المحتملة (المطابقة، والإدراج، والحذف المذكورة أعلاه) لمعرفة مصدرها. إذا كانت مطابقة، فـ $A_{i}$ و $B_{j}$ إذا كانت متطابقة، فاحذفها، ثم $A_{i}$ يتم محاذاته مع وجود فجوة، وإذا تم إدراجه، فـ $B_{j}$ يتماشى مع فجوة. (بشكل عام، قد يكون لأكثر من خيار نفس القيمة، مما يؤدي إلى محاذاة مثالية بديلة.)

AlignmentA ← "" AlignmentB ← "" i ← الطول (أ) j ← طول (B) بينما (i > 0 أو j > 0) { إذا كان (i > 0 و j > 0 و F(i, j) == F(i−1, j−1) + S(A _i , B _j )) { AlignmentA ← A _i + AlignmentA AlignmentB ← B _j + AlignmentB i ← i − 1 j ← j − 1 } وإلا إذا (i > 0 و F(i, j) == F(i−1, j) + d) { AlignmentA ← A _i + AlignmentA AlignmentB ← "−" + AlignmentB i ← i − 1 } آخر { محاذاة أ ← "-" + محاذاة أ AlignmentB ← B _j + AlignmentB j ← j − 1 } }

تعقيد

حساب النتيجة $F_{ij}$ لكل خلية في الجدول $O(1)$ العملية. وبالتالي فإن التعقيد الزمني للخوارزمية لتسلسلين بطول $n$ و $m$ يكون $O(mn)$ [ ^{3 ]} لقد ثبت أنه من الممكن تحسين وقت التشغيل ^إلى $O(mn/\log n)$ باستخدام طريقة الروس الأربعة . ^{[ 3 ]}^{[ 4 ]} بما أن الخوارزمية تملأ $n\times m$ الجدول الذي يمثل تعقيد المساحة هو $O(mn).$ ^{[ 3 ]}

ملاحظات تاريخية وتطوير الخوارزميات

كان الغرض الأصلي من الخوارزمية التي وصفها نيدلمان وونش هو إيجاد أوجه التشابه في تسلسل الأحماض الأمينية لبروتينين. ^{[ 1 ]}

يصف نيدلمان وونش خوارزميتهما صراحةً في حالة معاقبة المحاذاة فقط من خلال التطابقات وعدم التطابقات، وعدم وجود عقوبة للفجوات ( d = 0). يشير المنشور الأصلي من عام 1970 إلى التكرار. $F_{ij}=\max _{h<i,k<j}\{F_{h,j-1}+S(A_{i},B_{j}),F_{i-1,k}+S(A_{i},B_{j})\}$ .

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

قد يُفرض عامل جزاء، وهو رقم يُخصم عن كل فجوة، كعائق أمام السماح بوجود هذه الفجوة. وقد يكون عامل الجزاء دالةً لحجم الفجوة و/أو اتجاهها. [صفحة 444]

تم تقديم خوارزمية برمجة ديناميكية أفضل ذات وقت تشغيل تربيعي لنفس المشكلة (بدون عقوبة الفجوة) لاحقًا ^{[ 5 ]} بواسطة ديفيد سانكوف في عام 1972. تم اكتشاف خوارزميات مماثلة ذات وقت تربيعي بشكل مستقل بواسطة تي كي فينتسيوك ^{[ 6 ]} في عام 1968 لمعالجة الكلام ( "تشويه الوقت" )، وبواسطة روبرت أ. فاغنر ومايكل ج. فيشر ^{[ 7 ]} في عام 1974 لمطابقة السلاسل.

صاغ نيدلمان وونش مشكلتهما من حيث تعظيم التشابه. وثمة احتمال آخر يتمثل في تقليل مسافة التحرير بين التسلسلات، وهو ما طرحه فلاديمير ليفنشتاين . وقد أثبت بيتر إتش. سيلرز ^{[ 8 ]} في عام 1974 أن المشكلتين متكافئتان.

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

ركزت التطورات الحديثة على تحسين وقت ومساحة تنفيذ الخوارزمية مع الحفاظ على جودتها. فعلى سبيل المثال، في عام 2013، اقترحت خوارزمية المحاذاة العالمية المثلى السريعة (FOGSAA) ^{[ 9 ]} محاذاة تسلسلات النيوكليوتيدات/البروتينات بشكل أسرع من طرق المحاذاة العالمية المثلى الأخرى، بما في ذلك خوارزمية نيدلمان-وونش. وتزعم الورقة البحثية أن خوارزمية FOGSAA، مقارنةً بخوارزمية نيدلمان-وونش، تحقق توفيرًا في الوقت يتراوح بين 70 و90% لتسلسلات النيوكليوتيدات شديدة التشابه (بنسبة تشابه تزيد عن 80%)، وبين 54 و70% للتسلسلات التي تتراوح نسبة تشابهها بين 30 و80%.

تطبيقات خارج نطاق المعلوماتية الحيوية

رؤية مجسمة حاسوبية

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

على الرغم من إمكانية تصحيح الصور في العديد من التطبيقات، كإعادة تقسيم الكاميرا أو معايرتها، إلا أن ذلك قد يكون مستحيلاً أو غير عملي في بعض الأحيان، نظراً للتكلفة الحسابية العالية لنماذج التصحيح الدقيقة التي تحول دون استخدامها في التطبيقات الآنية . علاوة على ذلك، لا يُناسب أي من هذه النماذج الحالات التي تُظهر فيها عدسة الكاميرا تشوهات غير متوقعة ، كتلك الناتجة عن قطرات المطر أو الأغطية المقاومة للعوامل الجوية أو الغبار. من خلال توسيع خوارزمية نيدلمان-وونش، يُمكن ربط خط في الصورة اليسرى بمنحنى في الصورة اليمنى، وذلك بإيجاد المحاذاة ذات أعلى درجة في مصفوفة ثلاثية الأبعاد. وقد أثبتت التجارب أن هذا التوسيع يُتيح مطابقة دقيقة للبكسلات بين الصور غير المصححة أو المشوهة. ^{[ 10 ]}

الشبكات العصبية الاصطناعية

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

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

انظر أيضاً

مراجع

1 2 3 نيدلمان، شاول ب. وونش، كريستيان د. (1970). "طريقة عامة قابلة للتطبيق على البحث عن أوجه التشابه في تسلسل الأحماض الأمينية لبروتينين". مجلة البيولوجيا الجزيئية . 48 (3): 443-53 . doi : 10.1016/0022-2836(70)90057-4 . PMID 5420325 .
↑ "المعلوماتية الحيوية" . تم الاطلاع عليه بتاريخ 10 سبتمبر 2014 .
1 2 3 وينغ-كين، سونغ (2010). الخوارزميات في المعلوماتية الحيوية : مقدمة عملية . بوكا راتون: تشابمان آند هول/سي آر سي برس. ص 34-35 . ISBN 9781420070330. OCLC 429634761 .
↑ ماسك، ويليام؛ باترسون، مايكل (فبراير 1980). "خوارزمية أسرع لحساب مسافات تحرير السلاسل النصية" . مجلة علوم الحاسوب والأنظمة . 20 : 18-31 . doi : 10.1016/0022-0000(80)90002-1 . hdl : 1721.1/148933 .
↑ سانكوف د (1972). "مطابقة التسلسلات في ظل قيود الحذف/الإدخال" . وقائع الأكاديمية الوطنية للعلوم في الولايات المتحدة الأمريكية . 69 (1): 4-6 . Bibcode : 1972PNAS...69....4S . doi : 10.1073 / pnas.69.1.4 . PMC 427531. PMID 4500555 .
↑ فينتسيوك، ت. ك. (1968). "تمييز الكلام بواسطة البرمجة الديناميكية". كيبيرنيتيكا . 4 : 81-88 . doi : 10.1007/BF01074755 . S2CID 123081024 .
↑ فاغنر، ر. أ.، وفيشر، م. ج. (1974). "مشكلة تصحيح الأوتار" . مجلة ACM . 21 (1): 168-173 . doi : 10.1145/321796.321811 . S2CID 13381535 .
↑ سيلرز، بي. إتش. (1974). "حول نظرية وحساب المسافات التطورية". مجلة SIAM للرياضيات التطبيقية . 26 (4): 787-793 . doi : 10.1137/0126070 .
↑ تشاكرابورتي، أنجانا؛ بانديوبادياي، سانغاميترا (29 أبريل 2013). "FOGSAA: خوارزمية محاذاة التسلسل العالمي الأمثل السريع" . التقارير العلمية . 3 : 1746. Bibcode : 2013NatSR...3.1746C . doi : 10.1038/srep01746 . PMC 3638164. PMID 23624407 .
↑ ثيفينون، ج؛ مارتينيز-ديل-رينكون، ج؛ دييني، ر؛ نيبيل، ج.س. (2012). مطابقة البكسلات الكثيفة بين الصور غير المصححة والمشوهة باستخدام البرمجة الديناميكية . المؤتمر الدولي لنظرية وتطبيقات رؤية الحاسوب. روما.
↑ آفيلا بافا، م؛ غروه، ر؛ كيست، أ.م. (2024). مقياس التشابه القائم على محاذاة التسلسل في البحث عن بنية الشبكات العصبية التطورية . المؤتمر الدولي للتعلم الآلي الآلي (AutoML 2024). باريس.

روابط خارجية

[Needleman-1] 1 2 3 نيدلمان، شاول ب. وونش، كريستيان د. (1970). "طريقة عامة قابلة للتطبيق على البحث عن أوجه التشابه في تسلسل الأحماض الأمينية لبروتينين". مجلة البيولوجيا الجزيئية . 48 (3): 443-53 . doi : 10.1016/0022-2836(70)90057-4 . PMID 5420325 .

[2] "المعلوماتية الحيوية" . تم الاطلاع عليه بتاريخ 10 سبتمبر 2014 .

[:0-3] 1 2 3 وينغ-كين، سونغ (2010). الخوارزميات في المعلوماتية الحيوية : مقدمة عملية . بوكا راتون: تشابمان آند هول/سي آر سي برس. ص 34-35 . ISBN 9781420070330. OCLC 429634761 .

[4] ماسك، ويليام؛ باترسون، مايكل (فبراير 1980). "خوارزمية أسرع لحساب مسافات تحرير السلاسل النصية" . مجلة علوم الحاسوب والأنظمة . 20 : 18-31 . doi : 10.1016/0022-0000(80)90002-1 . hdl : 1721.1/148933 .

[Sankoff-5] سانكوف د (1972). "مطابقة التسلسلات في ظل قيود الحذف/الإدخال" . وقائع الأكاديمية الوطنية للعلوم في الولايات المتحدة الأمريكية . 69 (1): 4-6 . Bibcode : 1972PNAS...69....4S . doi : 10.1073 / pnas.69.1.4 . PMC 427531. PMID 4500555 .

[Vintsyuk-6] فينتسيوك، ت. ك. (1968). "تمييز الكلام بواسطة البرمجة الديناميكية". كيبيرنيتيكا . 4 : 81-88 . doi : 10.1007/BF01074755 . S2CID 123081024 .

[WagnerFischer-7] فاغنر، ر. أ.، وفيشر، م. ج. (1974). "مشكلة تصحيح الأوتار" . مجلة ACM . 21 (1): 168-173 . doi : 10.1145/321796.321811 . S2CID 13381535 .

[Sellers-8] سيلرز، بي. إتش. (1974). "حول نظرية وحساب المسافات التطورية". مجلة SIAM للرياضيات التطبيقية . 26 (4): 787-793 . doi : 10.1137/0126070 .

[9] تشاكرابورتي، أنجانا؛ بانديوبادياي، سانغاميترا (29 أبريل 2013). "FOGSAA: خوارزمية محاذاة التسلسل العالمي الأمثل السريع" . التقارير العلمية . 3 : 1746. Bibcode : 2013NatSR...3.1746C . doi : 10.1038/srep01746 . PMC 3638164. PMID 23624407 .

[10] ثيفينون، ج؛ مارتينيز-ديل-رينكون، ج؛ دييني، ر؛ نيبيل، ج.س. (2012). مطابقة البكسلات الكثيفة بين الصور غير المصححة والمشوهة باستخدام البرمجة الديناميكية . المؤتمر الدولي لنظرية وتطبيقات رؤية الحاسوب. روما.

[11] آفيلا بافا، م؛ غروه، ر؛ كيست، أ.م. (2024). مقياس التشابه القائم على محاذاة التسلسل في البحث عن بنية الشبكات العصبية التطورية . المؤتمر الدولي للتعلم الآلي الآلي (AutoML 2024). باريس.

[١]

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]