T-Coffee: a novel method for fast and accurate multiple sequence alignment. We describe a new method (T-Coffee) for multiple sequence alignment that provides a dramatic improvement in accuracy with a modest sacrifice in speed as compared to the most commonly used alternatives. The method is broadly based on the popular progressive approach to multiple alignment but avoids the most serious pitfalls caused by the greedy nature of this algorithm. With T-Coffee we pre-process a data set of all pair-wise alignments between the sequences. This provides us with a library of alignment information that can be used to guide the progressive alignment. Intermediate alignments are then based not only on the sequences to be aligned next but also on how all of the sequences align with each other. This alignment information can be derived from heterogeneous sources such as a mixture of alignment programs and/or structure superposition. Here, we illustrate the power of the approach by using a combination of local and global pair-wise alignments to generate the library. The resulting alignments are significantly more reliable, as determined by comparison with a set of 141 test cases, than any of the popular alternatives that we tried. The improvement, especially clear with the more difficult test cases, is always visible, regardless of the phylogenetic spread of the sequences in the tests.

References in zbMATH (referenced in 15 articles )

Showing results 1 to 15 of 15.
Sorted by year (citations)

  1. Pesch, Robert: Cross-species network and transcript transfer (2016)
  2. Mora-Gutiérrez, Roman Anselmo; Lárraga-Ramírez, María E.; Rincón-García, Eric A.; Ponsich, Antonin; Ramírez-Rodríguez, Javier: Adaptation of the method of musical composition for solving the multiple sequence alignment problem (2015)
  3. Federico, Maria; Peterlongo, Pierre; Pisanti, Nadia; Sagot, Marie-France: Rime: repeat identification (2014)
  4. Le Thi, Hoai An; Dinh, Tao Pham; Belghiti, Moulay: DCA based algorithms for multiple sequence alignment (MSA) (2014)
  5. Daugelaite, Jurate; O’Driscoll, Aisling; Sleator, Roy D.: An overview of multiple sequence alignments and cloud computing in bioinformatics (2013)
  6. Andoni, Alexandr; Daskalakis, Constantinos; Hassidim, Avinatan; Roch, Sebastien: Global alignment of molecular sequences via ancestral state reconstruction (2012)
  7. Petitjean, François; Gançarski, Pierre: Summarizing a set of time series by averaging: from Steiner sequence to compact multiple alignment (2012)
  8. Petitjean, François; Ketterlin, Alain; Gançarski, Pierre: A global averaging method for dynamic time warping, with applications to clustering (2011)
  9. Lloyd, Scott; Snell, Quinn O.: Hardware accelerated sequence alignment with traceback (2009)
  10. Althaus, Ernst; Canzar, Stefan: A Lagrangian relaxation approach for the multiple sequence alignment problem (2008)
  11. Machado-Lima, Ariane; del Portillo, Hernando A.; Durham, Alan Mitchell: Computational methods in noncoding RNA research (2008)
  12. Althaus, Ernst; Caprara, Alberto; Lenhof, Hans-Peter; Reinert, Knut: A branch-and-cut algorithm for multiple sequence alignment (2006)
  13. Wen, Zhining; Wang, Kelong; Li, Menglong; Nie, Fusheng; Yang, Yi: Analyzing functional similarity of protein sequences with discrete wavelet transform (2005)
  14. Zhang, Min; Fang, Weiwu; Zhang, Junhua; Chi, Zhongxian: MSAID: multiple sequence alignment based on a measure of information discrepancy (2005)
  15. Wang, Yi; Li, Kuo-Bin: An adaptive and iterative algorithm for refining multiple sequence alignment (2004)