Gelen Teorik Bilgisayar Bilimi ve özellikle algoritmik metin , en yakın zincir (İngilizce yakın dize bir dizi) karakter dizeleri verilerine göre, bir minimum mesafe kanal dizeleri olduğunu Hamming mesafesi . En yakın zinciri için arama bir olan algoritmik problemi NP-zor .
Beş zincir için
BARAKADABRA |
ABRAACDABRA |
RBRACADABCA |
ACRACADABCA |
ABRADADABCA |
en yakın kanal
ABRACADABRA |
Verilen kanallardan uzak 2'dir. Tesadüfler kırmızıyla işaretlenmiştir:
BA RACADABRA |
ABRA AC DABRA |
R BİLEZİK C C |
A C RACADAB C A |
ABRA D ADAB C A |
Verilen n zincirler s 1 , ..., s , n aynı uzunluğu m , yakın zincirli sorun , yeni bir zincir belirlenmesine dayanır s uzunluğu m , öyle ki d ( s , s , i ) ≤ k tüm i , d olan Hamming uzaklığı ve burada k mümkün olduğunca küçük. İlgili karar problemi olan, NP-tam da tamsayı alır k girdi olarak ve en fazla Hamming uzaklığı olan bir dize varsa sorar k tüm verilen dizeleri. Sorun, ikili bir alfabede bile NP-zordur.
Gelen Biyoinformatik , en yakın zincirli sorun, sinyal algılama sorun çok çalışılmış bir yönü konu olan DNA'ların . Problemin kod teorisinde de uygulamaları vardır (minimum yarıçap problemi). En yakın substring problemi, korunan bölgelerin araştırılmasında, genetik ilaç hedeflerinin tanımlanmasında ve moleküler biyolojide genetik probların üretilmesinde biyolojik uygulamaları resmileştirir. Gelen metin algoritmalarıyla , bu karakter dizeleri kombinatorik bir sorundur. Bu zincir problemi ve metin madenciliğinden biyolojik sekans analizine kadar çeşitli uygulamalarda ortaya çıkan diğerleri genellikle NP açısından zordur . Bu , bu sorunların özel sabit parametreli izlenebilir durumlarının araştırılmasını motive eder . Bu, alfabenin boyutu, tel sayısı veya mesafenin üst sınırı gibi doğal olarak ilişkili birkaç parametrenin olduğu durumlarda anlamlıdır.
En yakın zincir problemi, mesafesi olarak Hamming mesafesi ile 1 merkez probleminin bir örneği olarak geometrik olarak görülebilir .
Problemin en yakın zincir örnekleri, problem için anlamlı olmayan veya başka bir deyişle problemin zorluğuna katkıda bulunmayan bilgiler içerebilir. Bazı şeritler karakteri içerebilir, örneğin, a , ve hiçbiri karakter içeren z her yerine a ile Z bir esas olarak eşdeğer bir örneğini verir modifiye edilmiş, örneğin bir çözeltiden, orijinal solüsyon kolayca geri ve tersi olabilir.
Girdi dizelerini birbirinin altına yazarak bir matris elde ederiz. Bazı hat türleri özünde çözüm üzerinde aynı etkilere sahiptir. Örneğin, girişlere ( a , a , b ) sahip bir sütunun bir sütun ( x , x , y ) ile değiştirilmesi farklı bir çözüm dizesine yol açabilir, ancak ödeme gücünü etkileyemez çünkü her iki sütun aynı yapıyı ifade eder., ilk iki giriş eşittir, ancak üçüncüsünden farklıdır.
Bir girdi örneği, her sütunda en sık ortaya çıkan karakterin a ile , ikinci olarak ortaya çıkan karakterin b ile değiştirilmesi vb. Yoluyla normalleştirilebilir . Normalleştirilmiş örneğin bir çözümü verildiğinde, orijinal örnek, çözümdeki karakterlerin her bir sütundaki orijinal sürümleriyle değiştirilmesiyle kurtarılabilir. Sütunların sırası, sorunun zorluğuna katkıda bulunmaz. Bu, girdi dizgelerini bazı permütasyon π 'ye göre değiştirirsek ve bu değiştirilmiş örneğe bir çözüm dizesi s alırsak , o zaman π −1 ( s ) orijinal örneğin bir çözümü olduğu anlamına gelir.
Uvwx , xuwv ve xvwu kelimelerinin oluşturduğu bir örneği ele alıyoruz (yukarıdaki şemaya bakınız). Bir matris biçiminde aşağıdaki tabloyu elde ederiz:
sen | v | w | x |
x | sen | w | v |
x | v | w | sen |
İlk sütunda ( u , x , x ), en sık (2 kez) görünen x sembolüdür ; biz ile değiştirin Bir ve karakter u tarafından b yeni ilk sütunu verir, ( b , a , a ). İkinci sütun ( v , u , v ) aynı strateji ile ( a , b , a ) ile değiştirilir. Diğer sütunlar için aynı şekilde ilerleyerek,
b | -de | -de | -de |
-de | b | -de | b |
-de | -de | -de | vs |
Normalleştirme, alfabenin boyutunun en fazla girdi dizgilerinin sayısına eşit olması sonucunu doğurur. Bu, hesaplama süresi alfabenin boyutuna bağlı olan algoritmalar için yararlı olabilir.
Li vd. polinom zamanında bir yaklaşım şeması tanımlamış , ancak bu, büyük gizli sabitler nedeniyle pratikte kullanılamaz.
En yakın dize sorunu çözülebilir O ( nL + ND x d d ) , burada n, giriş olarak verilen şeritlerinin sayısını, L tüm dizileri ortak uzunluğu ve D verilen tüm için çözeltiden istenen mesafe Teller. Bu nedenle , parametreli karmaşıklık FPT ( sabit parametreli izlenebilir ) sınıfındadır .
En yakın zincir problemi, en yakın alt dizgenin (in) daha genel probleminin özel bir durumudur , kesinlikle daha zordur. En yakın zincir problemi sabit parametrelerle farklı şekillerde izlenebilirken , W [1] alt dize problemi bu parametrelere göre zordur . Kernelization Bu ve ilgili sorunlardan biri karmaşıklığı teoride varsayımlarda altında elde edilemez bir polinom çekirdek veya bu tür bir çekirdek alabileceği gösterir detaylı bir çalışma konusu olmuştur ve özellikle de vardır üstel saat Hipotez (ETH ). Bu sorunlar, belirli bir zincir seti için ortak olan bir alt yapı veya üst yapı bulmaktır. En temel sorunlardır en uzun ortak sonradan , en kısa yaygın süper dizisi, ve en küçük ortak dizisi. Ek olarak, biyolojik sekans analizinde son derece önemli olan çoklu sekans hizalamasına ilişkin daha genel bir problem vardır .