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 cl

SUBMITTER: Blackshields G 

PROVIDER: S-EPMC2893182 | biostudies-literature | 2010 May

REPOSITORIES: biostudies-literature