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

Files in This Item:
File Description SizeFormat 
1748-7188-5-21.pdf1.04 MBAdobe PDFDownload
Title: Sequence embedding for fast construction of guide trees for multiple sequence alignment
Authors: Blackshields, Gordon
Sievers, Fabian
Shi, Weifeng
Wilm, Andreas
Higgins, D. (Des)
Permanent link:
Date: 14-May-2010
Abstract: 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. 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. 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
Funding Details: Science Foundation Ireland
Type of material: Journal Article
Publisher: BioMed Central
Journal: Algorithms for Molecular Biology
Volume: 5
Issue: 21
Start page: 1
End page: 11
Copyright (published version): 2010 the Authors
Keywords: DNA sequencingInput sequencesEmbeddingmBed
DOI: 10.1186/1748-7188-5-21
Language: en
Status of Item: Peer reviewed
Appears in Collections:Conway Institute Research Collection
Medicine Research Collection

Show full item record

Citations 5

Last Week
Last month
checked on Nov 12, 2018

Download(s) 50

checked on May 25, 2018

Google ScholarTM



This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.