التقريبية سلسلة خوارزميات مطابقة
https://stackoverflow.com/questions/49263
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هنا في العمل ، ونحن غالبا ما تحتاج إلى العثور على سلسلة من قائمة السلاسل التي هي أقرب مباراة إلى أخرى سلسلة الإدخال.حاليا نحن نستخدم نيدلمان-ونش الخوارزمية.الخوارزمية غالبا ما يعود الكثير من كاذبة ايجابيات (إذا وضعنا الحد الأدنى من درجة منخفضة جدا), في بعض الأحيان لا تجد المباراة عندما ينبغي (عند الحد الأدنى درجة عالية جدا) ، أكثر من مرة ، نحن بحاجة إلى التحقق من النتائج من خلال اليد.نعتقد أننا يجب أن نحاول بدائل أخرى.
هل لديك أي تجارب مع الحسابية ؟ هل تعرف كيف الخوارزميات مقارنة أحد آخر ؟
أقدر لك بعض النصائح.
PS:نحن الترميز في C#, ولكن يجب أن أهتم أنا أسأل عن الخوارزميات بشكل عام.
آسف نسيت أن أذكر ذلك.
لا, نحن لا تستخدم لمطابقة البيانات المكررة.لدينا قائمة من السلاسل التي نحن نبحث عن نحن نسميها البحث-قائمة.ثم نحن بحاجة إلى عملية النصوص من مصادر مختلفة (مثل آر إس إس ، مواقع ، منتديات ، وغيرها.) - استخراج أجزاء من تلك النصوص (هناك مجموعات بأكملها من القواعد لذلك ، ولكن هذا ليس له علاقة بالموضوع) ونحن بحاجة إلى تطابق تلك ضد البحث-قائمة.إذا كانت السلسلة مباريات واحدة من السلاسل في البحث-قائمة - نحن بحاجة إلى القيام ببعض مزيد من المعالجة من الشيء (الذي هو أيضا غير ذي صلة).
ونحن لا يمكن أن تؤدي العادي المقارنة لأن الخيوط المستخرجة من مصادر خارجية ، أكثر من مرة ، إضافة بعض الكلمات.... الخ
على أية حال, ليس من أجل الكشف عن التكرارات.
المحلول
حسنا, نيدلمان-ونش(NW) هو كلاسيكي من النهاية إلى النهاية ("العالمية") المقوم من المعلوماتية الحيوية الأدب.كان منذ فترة طويلة كما تتوفر "محاذاة" و "align0" في FASTA الحزمة.الفرق هو أن "0" نسخة لم تكن منحازة حول تجنب نهاية فجوات ، والتي غالبا ما سمح تفضيل عالية الجودة الداخلي مباريات أسهل.سميث-الملاح, وأظن أنك تعلم المحلية المقوم و هو الأساس الأصلي الانفجار.FASTA كان هو نفسه المحلية المقوم وكذلك كان مختلفا قليلا.كل هذه هي أساسا ارشادي أساليب تقدير Levenshtein المسافة ذات الصلة إلى التهديف متري على شخصية الفرد أزواج (في المعلوماتية الحيوية ، وغالبا ما تعطى من قبل Dayhoff/"بام", Henikoff&Henikoff ، أو غيرها من المصفوفات و عادة استبدال شيء أبسط وأكثر معقولة تعكس بدائل اللغوية كلمة التشكل عند تطبيقها على اللغة الطبيعية).
دعونا لا يكون الثمينة عن التسميات:Levenshtein المسافة المشار إليها في الممارسة على الأقل ، هو في الأساس تحرير المسافة وعليك أن تقدير ذلك لأنه ليس من الممكن حساب ذلك عموما انها باهظة الثمن لحساب بالضبط حتى مثيرة للاهتمام في حالات خاصة:يحصل على المياه العميقة سريعة هناك ، وبالتالي لدينا أساليب الكشف عن مجريات الأمور من سمعة طيبة.
إن المشكلة الخاصة بك:قبل عدة سنوات كنت قد للتحقق من دقة قصيرة من الحمض النووي يقرأ ضد المرجعية التسلسل المعروف أن تكون صحيحة و لا جاء بشيء يسمى "الراسية التحالفات".
والفكرة هي أن تأخذ المرجعية سلسلة و "هضم" قبل العثور على جميع أماكن معينة ن-شخصية فرعية يحدث.اختيار N بحيث يكون الجدول بناء ليست كبيرة جدا ولكن أيضا بحيث سلاسل فرعية من طول N ليست شائعة جدا.على الحروف الهجائية الصغيرة مثل الحمض النووي القواعد ، فمن الممكن أن تأتي مع الكمال تجزئة على أوتار الأحرف ن و جعل الجدول سلسلة المباريات في قائمة مرتبطة من كل بن.قائمة الإدخالات يجب تحديد تسلسل بدء موقف فرعية أن الخرائط بن الذين في قائمة حدوثها.هذه هي "المراسي" في قائمة السلاسل التي سيتم البحث فيها NW المحاذاة من المرجح أن تكون مفيدة.
عند معالجة سلسلة الاستعلام ، خذ ن الأحرف التي تبدأ في بعض تعويض K في سلسلة الاستعلام ، تجزئة لهم ، ابحث عن الحاويات ، إذا كانت قائمة على أن بن هو غير فارغ ثم تذهب من خلال جميع قائمة السجلات وإجراء التحالفات بين سلسلة الاستعلام و البحث سلسلة المشار إليها في المحضر.عندما تفعل هذه التحالفات ، تصطف سلسلة الاستعلام و البحث سلسلة في مرساة واستخراج سلسلة فرعية من سلسلة البحث هذا هو نفس طول سلسلة الاستعلام الذي يحتوي على هذا الربط في نفس الإزاحة, K.
إذا اخترت طويلة بما فيه الكفاية مرساة طول ن ، و مجموعة معقولة من قيم الإزاحة ك (أنها يمكن أن تنتشر عبر سلسلة الاستعلام أو تكون مقيدة إلى انخفاض إزاحة) يجب أن تحصل على مجموعة فرعية من الممكن التحالفات و في كثير من الأحيان سوف تحصل على أكثر وضوحا الفائزين.عادة سوف تحتاج إلى استخدام أقل نهاية منحازة align0 مثل NW المقوم.
هذا الأسلوب يحاول تعزيز NW قليلا عن طريق تقييد انها المدخلات هذا الأداء مكسب لأنك لا أقل التحالفات وهم في كثير من الأحيان بين مماثل متواليات.آخر شيء جيد القيام به مع الخاص بك NW المقوم هو أن تسمح لها أن تتخلى عن بعد بعض المبلغ أو طول فجوات يحدث لخفض التكاليف, خاصة إذا كنت تعرف أنك لن ترى أو تكون مهتمة في باعتدال-نوعية المباريات.
وأخيرا ، تم استخدام هذا الأسلوب على نظام مع الحروف الهجائية الصغيرة ، مع ك يقتصر على أول 100 أو حتى مناصب في سلسلة الاستعلام و مع سلاسل البحث أكبر بكثير من الاستعلامات (الحمض النووي يقرأ حوالي 1000 أسس البحث السلاسل كانت في حدود 10000, إذا كنت تبحث عن التقريبية فرعية مباريات تبرره تقدير تحرير المسافة على وجه التحديد).تكييف هذه المنهجية إلى اللغة الطبيعية سوف تتطلب بعض التفكير بعناية:تفقد على الأبجدية الحجم ولكن يمكنك الحصول على إذا كان لديك سلاسل الاستعلام و البحث سلاسل من نفس الطول.
وفي كلتا الحالتين ، مما يتيح أكثر من مرساة من نهايات مختلفة من سلسلة الاستعلام لاستخدامها في وقت واحد قد تكون مفيدة في زيادة تصفية البيانات الاحتياطي الفيدرالي إلى NW.إذا فعلت هذا تكون مستعدة لاحتمال إرسال تداخل السلاسل تحتوي كل منها على واحد من اثنين من المراسي إلى المقوم ثم التوفيق بين التحالفات...أو ربما تعديل NW التأكيد على الحفاظ على المراسي في الغالب سليمة خلال محاذاة باستخدام عقوبة التعديل خلال الخوارزمية التنفيذ.
نأمل أن يكون هذا مفيدا أو على الأقل مثيرة للاهتمام.
نصائح أخرى
تتعلق واستعرضت اللجنة بعد:قد ترغب في تطبيع ذلك بقسمة النتيجة مع طول أطول سلسلة, بحيث يمكنك دائما الحصول على رقم بين 0 و 1 و بحيث يمكنك مقارنة المسافة من زوج من السلاسل بطريقة ذات معنى (التعبير L(A, B) > L(أ ، ج) - على سبيل المثال - لا معنى له إلا إذا كنت تطبع بعد).
خوارزميات بديلة إلى أن ننظر إلى agrep (ويكيبيديا على agrep), FASTA والانفجار البيولوجية تسلسل خوارزميات مطابقة.هذه هي حالات خاصة من التقريبية سلسلة مطابقة, أيضا في ستوني بروك خوارزمية repositry.إذا كان يمكنك تحديد طرق السلاسل تختلف عن بعضها البعض ، ربما يمكن التركيز على مصممة الخوارزمية.على سبيل المثال ، aspell يستخدم بعض البديل "soundslike" (soundex-metaphone) المسافة في تركيبة مع "المفاتيح" المسافة لاستيعاب سيئة المتهجون سيئة typers على حد سواء.
نحن نستخدم Levenshtein المسافة طريقة للتحقق من تكرار العملاء في قاعدة البيانات الخاصة بنا.أنه يعمل بشكل جيد جدا.
بغية التقليل إلى أدنى حد التطابق بسبب اختلافات طفيفة أو أخطاء في الإملاء ، لقد استعملت Metaphone الخوارزمية ، ثم Levenshtein المسافة (تحجيم 0-100 كنسبة مئوية مباراة) على Metaphone ترميزات قدرا من التقارب.يبدو أن عملت بشكل جيد.
إلى التوسع في Cd-الرجل الجواب ، يبدو أنك تواجه مشكلة التطبيع.ليس من الواضح كيفية التعامل مع عشرات بين التحالفات مع فترات متفاوتة.
بالنظر إلى ما كنت مهتما في, قد ترغب في الحصول على p-قيم المحاذاة.إذا كنت تستخدم نيدلمان-ونش, يمكنك الحصول على هذه القيم ص باستخدام كارلين-Altschul الإحصاءات http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html
الانفجار لن تستطيع المواءمة المحلية وتقييمها باستخدام هذه الإحصاءات.إذا كنت تشعر بالقلق إزاء السرعة ، وهذا من شأنه أن يكون أداة جيدة للاستخدام.
وثمة خيار آخر هو استخدام HMMER.HMMER يستخدم ملف تعريف نماذج ماركوف المخفية إلى محاذاة متواليات.أنا شخصيا أعتقد أن هذا هو نهج أكثر قوة لأنه كما يوفر المعلومات الموضعية. http://hmmer.janelia.org/
كنت أعمل مع بعض من أقذر البيانات سوف تجد من أي وقت مضى.في المتوسط حوالي 5000 صفوف من البيانات (أي ما يعادل مئات الآلاف من الدولارات) المطلوبة مطابقة تماما مرهقة.أول تجربة لي مع مطابقة غامض كان خوارزمية من السيد Excel مكتوب في VBA.وكان بعض القضايا مع الاتساق في الأشياء التي كنت أتوقع أن يكون صفر في المئة لم تكن ثا و الأشياء التي كانت حوالي 60 في المئة بدا أكثر من 90 في المئة.لذا انتقلت إلى Levenshtein ثم في وقت لاحق Damerau-Levenshtein.هذا هو تحسن كبير ولكن بطيئة جدا في Excel.أنا القادم تخطي إلى Jaro-وينكلر ولكن انخفض بسرعة بعد ذلك بوقت قصير.وأخيرا في عام 2016 كتبت بلدي (على أساس n-غرام) و المكرر أنه على مدى السنوات القادمة 2.اليوم هو إضافة على ما يسمى Flookup;يمكنك الحصول على جداول بيانات Google و نرى كيف يحمل ما يصل.
