Sequence embedding for fast construction of guide trees for multiple sequence alignment

Hdl Handle:
http://hdl.handle.net/10147/119666
Title:
Sequence embedding for fast construction of guide trees for multiple sequence alignment
Authors:
Blackshields, Gordon; Sievers, Fabian; Shi, Weifeng; Wilm, Andreas; Higgins, Desmond G
Citation:
Algorithms for Molecular Biology. 2010 May 14;5(1):21
Issue Date:
14-May-2010
URI:
http://hdl.handle.net/10147/119666
Abstract:
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 N 2 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.
Item Type:
Journal Article

Full metadata record

DC FieldValue Language
dc.contributor.authorBlackshields, Gordon-
dc.contributor.authorSievers, Fabian-
dc.contributor.authorShi, Weifeng-
dc.contributor.authorWilm, Andreas-
dc.contributor.authorHiggins, Desmond G-
dc.date.accessioned2011-01-18T11:36:33Z-
dc.date.available2011-01-18T11:36:33Z-
dc.date.issued2010-05-14-
dc.identifierhttp://dx.doi.org/10.1186/1748-7188-5-21-
dc.identifier.citationAlgorithms for Molecular Biology. 2010 May 14;5(1):21-
dc.identifier.urihttp://hdl.handle.net/10147/119666-
dc.description.abstractAbstract 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 N 2 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.-
dc.titleSequence embedding for fast construction of guide trees for multiple sequence alignment-
dc.typeJournal Article-
dc.language.rfc3066en-
dc.rights.holderBlackshields et al.; licensee BioMed Central Ltd.-
dc.description.statusPeer Reviewed-
dc.date.updated2010-12-16T07:04:25Z-
All Items in Lenus, The Irish Health Repository are protected by copyright, with all rights reserved, unless otherwise indicated.