title: Sequence embedding for fast construction of guide trees for multiple sequence alignment.
abstract: BACKGROUND
  The most widely used multiple sequence alignment methods require sequences to be clustered as an initial step. Most sequence clustering methods require a full distance matrix to be computed between all pairs of sequences. This requires memory and time proportional to N2 for N sequences. When N grows larger than 10,000 or so, this becomes increasingly prohibitive and can form a significant barrier to carrying out very large multiple alignments.
  
  
  RESULTS
  In this paper, we have tested variations on a class of embedding methods that have been designed for clustering large numbers of complex objects where the individual distance calculations are expensive. These methods involve embedding the sequences in a space where the similarities within a set of sequences can be closely approximated without having to compute all pair-wise distances.
  
  
  CONCLUSIONS
  We show how this approach greatly reduces computation time and memory requirements for clustering large numbers of sequences and demonstrate the quality of the clusterings by benchmarking them as guide trees for multiple alignment. Source code is available for download from http://www.clustal.org/mbed.tgz.
authors.affiliation: UCD Conway Institute of Biomolecular and Biomedical Sciences, University College Dublin, Dublin 4, Ireland. fabian.sievers@ucd.ie.
authors.forename: Gordon
authors.initials: G
authors.lastname: Blackshields
authors.forename: Fabian
authors.initials: F
authors.lastname: Sievers
authors.forename: Weifeng
authors.initials: W
authors.lastname: Shi
authors.forename: Andreas
authors.initials: A
authors.lastname: Wilm
authors.forename: Desmond G
authors.initials: DG
authors.lastname: Higgins
references.citation: Bioinformatics. 2007 Nov 1;23(21):2947-8
references.pmid: 17846036
references.citation: Nucleic Acids Res. 2002 Jul 15;30(14):3059-66
references.pmid: 12136088
references.citation: Proteins. 2005 Oct 1;61(1):127-36
references.pmid: 16044462
references.citation: J Mol Biol. 2000 Sep 8;302(1):205-17
references.pmid: 10964570
references.citation: Proteins. 1997 Jul;28(3):405-20
references.pmid: 9223186
references.citation: Comput Biol Chem. 2008 Aug;32(4):282-6
references.pmid: 18450519
references.citation: Mol Biol Evol. 1987 Jul;4(4):406-25
references.pmid: 3447015
references.citation: Genome Res. 2005 Feb;15(2):330-40
references.pmid: 15687296
references.citation: J Mol Evol. 1984;20(2):175-86
references.pmid: 6433036
references.citation: J Mol Biol. 1970 Mar;48(3):443-53
references.pmid: 5420325
references.citation: Protein Sci. 1998 Nov;7(11):2469-71
references.pmid: 9828015
references.citation: Bioinformatics. 2008 Jul 1;24(13):i41-9
references.pmid: 18586742
references.citation: Bioinformatics. 1999 Jan;15(1):87-8
references.pmid: 10068696
references.citation: Nucleic Acids Res. 2006 Jan 1;34(Database issue):D247-51
references.pmid: 16381856
references.citation: J Mol Biol. 1997 May 2;268(2):539-56
references.pmid: 9159489
references.citation: Nucleic Acids Res. 2004 Mar 19;32(5):1792-7
references.pmid: 15034147
references.citation: J Mol Evol. 1987;25(4):351-60
references.pmid: 3118049
references.citation: Bioinformatics. 2007 Apr 1;23(7):802-8
references.pmid: 17267437
references.citation: Comput Appl Biosci. 1987 Jun;3(2):81-7
references.pmid: 3453222
references.citation: Nucleic Acids Res. 2009 Jan;37(Database issue):D141-5
references.pmid: 19004872
references.citation: Bioinformatics. 2007 Feb 1;23(3):372-4
references.pmid: 17118958
references.citation: Nucleic Acids Res. 2005 Jan 1;33(Database issue):D121-4
references.pmid: 15608160
references.citation: Nucleic Acids Res. 1994 Nov 11;22(22):4673-80
references.pmid: 7984417
references.citation: Brief Bioinform. 2008 Jul;9(4):286-98
references.pmid: 18372315
references.citation: Proc Natl Acad Sci U S A. 1983 Feb;80(3):726-30
references.pmid: 6572363