多序列比對（最長公共子序列）？

獲得超過兩個字符串和「對齊」他們（無DNA/RNA序列或與他們每個人不喜歡1000級的物品等等，只是普通的字符串）

我已經做了一些成對比對的工作（對齊兩個字符串），但是「間隙」在嘗試對齊多對時會給我造成一些問題。

例（一個我目前正在測試）：

ABCDEF 
ABGHCEEF 
AJKLBCDYEOF 

AB--CDEF 
ABGHCEEF 
======================= 
AB--C-EF 

A-B--C--E-F 
AJKLBCDYEOF 
======================= 
A----C--E-F

而另一（多個解說）例如：

http://nest.drkameleon.com 
http://www.google.com 
http://www.yahoo.com 

http://nest.drkameleon.com 
http://-www.--google--.com 

======================= 
http://----.------le--.com 

http://----.------le--.com 
http://-www.-----yahoo.com 

======================= 
http://----.----------.com

我目前在做什麼：

排序的字符串（長字符串來第一次在列表中）
對準第一對：AB和得到的結果（假設R1）
然後對齊第二對：R1和C（結果R2）
然後對齊第三對：R2和D
等等...

那麼什麼是在你的心中？我怎麼能這樣做？有沒有更好的辦法？（當然，必須有...）

我寧願在Perl/Python或這些行上做這些事情，但是任何類型的代碼/引用都會受到歡迎！ :-)

來源

2012-04-09 Dr.Kameleon

你可能會張貼一些輸入和輸出的例子嗎？我不是100％的你想要做什麼。 – 2012-04-09 13:03:15

也看看這篇文章，詳細解釋了Python中的LCS問題。 http://wordaligned.org/articles/longest-common-subsequence#toc21 – luke14free 2012-04-09 13:05:48

@ Li-aungYip下面是我的意思：http://stackoverflow.com/questions/10065293/how-to-align-2-strings – 2012-04-09 13:10:37

我想你也許可以投這個問題是一個更一般的字符串差異問題，而不是字符串對準的。考慮如何使用GNU diff來查找兩個文件之間的差異，並使用與用於執行N路diff相同的算法。

我不確定這種方法的時間/內存複雜性是否適合您的需求，但您至少可以這樣思考問題。

來源

2012-04-09 13:18:19

我並不確定在這種情況下'diff'有多大幫助...... – 2012-04-09 15:48:08

有一種基於Levenshtein算法計算最長公共序列的算法，可選空間。不知道這是否有幫助。

來源

2012-04-09 15:46:38 Alberto

呃，顯然我在Levenshtein算法上玩了很多，然後試了一下Hirschberg的算法，但是可能會更接近我案例是** Needleman-Wunsch算法**（http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm） – 2012-04-09 15:50:10

多序列比對（最長公共子序列）？

回答

相關問題