ClustalW是现在用的最广和最经典的多序列比对软件, Muscle是速度最快的多序列比对之一,T-coffee是越来越受到欢迎的软件.它们各自有什么优点和缺点呢?

ClustalW不仅可以用来做多序列比对,也能做Profile-profile比对,以及基于Neighbor-joining方法构建进化树.但是最常用的是多序列比对.从速度上来说,它有两种运行模式:accurate,slow 和fast,appropriate.即使是fast模式它的速度也不如Muscle,但是slow模式也比T-coffee要快.

ClustalW的基本原理是首先做序列的两两比对,根据该两两比对计算两两距离矩阵,然后用NJ或者UPGMA方法构建Binary进化树作为guide tree,最后用progressive的方法根据guide tree逐步添加序列进行比对,一直到所有序列都比对好.

Muscle的功能仅限于多序列比对,它的最大优势是速度,比clustalw的速度快几个数量级,而且序列数越多速度的差别越大.它的时间复杂度为O(NL^2+N^3L),空间复杂度为O(N^2+NL+L^2).它之所以比clustalw快一方面是因为没有进行两两序列比对,用序列间共有的word数表征序列间的相似性;另一方面用UPGMA代替NJ构建guide tree. 如果没有对于结果的refinement过程,时间更短,时间复杂度为O(NL^2),也就是说时间和序列数成线性关系.一个形象的例子是,5000条长度为350的数据进行比对只需要7分钟,而用Clustalw则可能需要1年. 尽管如此,muscle对于内存的要求较高,从它的空间复杂度可以看出来.

T-coffee之所以广受欢迎可能是因为它的准确度和强大的功能.它能够整合很多信息,如结构信息,实验数据等用于序列比对.它的基本原理是首先构建一个库包含有clustalw得到的序列两两比对和fasta得到的局部两两比对,并且给每个比对一个权重.然后把全局比对和局部比对的结果进行整合,每个两两比对中每个位点的比对都是综合了库中该两两比对的序列和其他序列比对的结果,这样就给该位点比对一个权重用以表明该位点的该比对在整个库中的合理性程度.最后是progressive比对过程..该方法的最大优势在于能够整合各种信息,所以它的可拓展性较强,从2000年出现以来到现在T-coffee得到了极大的发展,功能非常丰富. 但是它的缺点是速度非常慢,其时间复杂度为O(N^2L^2)+O(N^3L)+O(N^3)+O(NL^2),因此数据集较小(n<100)的时候用它比较合适.

以上是三个软件的比较简单的比较,如果想知道的更具体需要看原始文献.需要注意的是,虽然从总体上来说,不同的软件的效果不一样,但是如果我们只是针对具体的问题想做一个比对,那么最好是综合几种方法得到的结果更可靠. 此外,当序列的相似性较高的时候(>80%),以上的任何一个软件的准确度都能够达到90%以上.

相关的论文:

ClustalW和ClustalX

ClustalW and ClustalX version 2 (2007) Larkin MA, Blackshields G, Brown NP, Chenna R, McGettigan PA, McWilliam H, Valentin F, Wallace IM, Wilm A, Lopez R, Thompson JD, Gibson TJ and Higgins DG .Bioinformatics 2007 23(21): 2947-2948. doi:10.1093/bioinformatics/btm404

A new bioinformatics analysis tools framework at EMBL-EBI (2010).Goujon M, McWilliam H, Li W, Valentin F, Squizzato S, Paern J, Lopez R.Nucleic acids research 2010 Jul, 38 Suppl: W695-9.doi:10.1093/nar/gkq313

Muscle

Edgar, Robert C. (2004), MUSCLE: multiple sequence alignment with high accuracy and high throughput, Nucleic Acids Research 32(5), 1792-97.

Edgar, Robert C (2004), MUSCLE: a multiple sequence alignment method with reduced time and space complexity. BMC Bioinformatics, 5(1):113.

T-coffee

T-Coffee: A novel method for multiple sequence alignments. Notredame,Higgins,Heringa,JMB,302(205-217)2000 [pdf][medline]

ClustalW是现在用的最广和最经典的多序列比对软件, Muscle是速度最快的多序列比对之一,T-coffee是越来越受到欢迎的软件.它们各自有什么优点和缺点呢?

ClustalW不仅可以用来做多序列比对,也能做Profile-profile比对,以及基于Neighbor-joining方法构建进化树.但是最常用的是多序列比对.从速度上来说,它有两种运行模式:accurate,slow 和fast,appropriate.即使是fast模式它的速度也不如Muscle,但是slow模式也比T-coffee要快.

ClustalW的基本原理是首先做序列的两两比对,根据该两两比对计算两两距离矩阵,然后用NJ或者UPGMA方法构建Binary进化树作为guide tree,最后用progressive的方法根据guide tree逐步添加序列进行比对,一直到所有序列都比对好.

Muscle的功能仅限于多序列比对,它的最大优势是速度,比clustalw的速度快几个数量级,而且序列数越多速度的差别越大.它的时间复杂度为O(NL^2+N^3L),空间复杂度为O(N^2+NL+L^2).它之所以比clustalw快一方面是因为没有进行两两序列比对,用序列间共有的word数表征序列间的相似性;另一方面用UPGMA代替NJ构建guide tree. 如果没有对于结果的refinement过程,时间更短,时间复杂度为O(NL^2),也就是说时间和序列数成线性关系.一个形象的例子是,5000条长度为350的数据进行比对只需要7分钟,而用Clustalw则可能需要1年. 尽管如此,muscle对于内存的要求较高,从它的空间复杂度可以看出来.

T-coffee之所以广受欢迎可能是因为它的准确度和强大的功能.它能够整合很多信息,如结构信息,实验数据等用于序列比对.它的基本原理是首先构建一个库包含有clustalw得到的序列两两比对和fasta得到的局部两两比对,并且给每个比对一个权重.然后把全局比对和局部比对的结果进行整合,每个两两比对中每个位点的比对都是综合了库中该两两比对的序列和其他序列比对的结果,这样就给该位点比对一个权重用以表明该位点的该比对在整个库中的合理性程度.最后是progressive比对过程..该方法的最大优势在于能够整合各种信息,所以它的可拓展性较强,从2000年出现以来到现在T-coffee得到了极大的发展,功能非常丰富. 但是它的缺点是速度非常慢,其时间复杂度为O(N^2L^2)+O(N^3L)+O(N^3)+O(NL^2),因此数据集较小(n<100)的时候用它比较合适.

以上是三个软件的比较简单的比较,如果想知道的更具体需要看原始文献.需要注意的是,虽然从总体上来说,不同的软件的效果不一样,但是如果我们只是针对具体的问题想做一个比对,那么最好是综合几种方法得到的结果更可靠. 此外,当序列的相似性较高的时候(>80%),以上的任何一个软件的准确度都能够达到90%以上.

相关的论文:

ClustalW和ClustalX

ClustalW and ClustalX version 2 (2007) Larkin MA, Blackshields G, Brown NP, Chenna R, McGettigan PA, McWilliam H, Valentin F, Wallace IM, Wilm A, Lopez R, Thompson JD, Gibson TJ and Higgins DG .Bioinformatics 2007 23(21): 2947-2948. doi:10.1093/bioinformatics/btm404

A new bioinformatics analysis tools framework at EMBL-EBI (2010).Goujon M, McWilliam H, Li W, Valentin F, Squizzato S, Paern J, Lopez R.Nucleic acids research 2010 Jul, 38 Suppl: W695-9.doi:10.1093/nar/gkq313

Muscle

Edgar, Robert C. (2004), MUSCLE: multiple sequence alignment with high accuracy and high throughput, Nucleic Acids Research 32(5), 1792-97.

Edgar, Robert C (2004), MUSCLE: a multiple sequence alignment method with reduced time and space complexity. BMC Bioinformatics, 5(1):113.

T-coffee

T-Coffee: A novel method for multiple sequence alignments. Notredame,Higgins,Heringa,JMB,302(205-217)2000 [pdf][medline]