Anticlustal: Multiple sequence alignment by antipole clustering and linear approximate 1-median computation

C. Di Pietro, V. Di Pietro, G. Emmanuele, A. Ferro, T. Maugeri, E. Modica, G. Pigola, A. Pulvirenti, M. Purrello, M. Ragusa, M. Scalia, D. Shasha, S. Travali, V. Zimmitti

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we present a new multiple sequence alignment (MSA) algorithm called AntiClustAl. The method makes use of the commonly used idea of aligning homologous sequences belonging to classes generated by some clustering algorithm, and then continue the alignment process in a bottom-up way along a suitable tree structure. The final result is then read at the root of the tree. Multiple sequence alignment in each cluster makes use of the progressive alignment with the 1-median (center) of the cluster. The 1-median of set S of sequences is the element of S which minimizes the average distance from any other sequence in S. Its exact computation requires quadratic time. The basic idea of our proposed algorithm is to make use of a simple and natural algorithmic technique based on randomised tournaments which has been successfully applied to large size search problems in general metric spaces. In particular a clustering algorithm called antipole tree and an approximate linear 1-median computation are used. Our algorithm compared with Clustal W, a widely used tool to MSA, shows a better running time results with fully comparable alignment quality. A successful biological application showing high amino acid conservation during evolution of Xenopus laevis SOD2 is also cited.

Original languageEnglish (US)
Title of host publicationProceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages326-336
Number of pages11
ISBN (Electronic)0769520006, 9780769520001
DOIs
StatePublished - 2003
Event2nd International IEEE Computer Society Computational Systems Bioinformatics Conference, CSB 2003 - Stanford, United States
Duration: Aug 11 2003Aug 14 2003

Publication series

NameProceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003

Other

Other2nd International IEEE Computer Society Computational Systems Bioinformatics Conference, CSB 2003
CountryUnited States
CityStanford
Period8/11/038/14/03

Keywords

  • Clustering
  • Multiple Sequence Alignment
  • Randomized Tournament

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Anticlustal: Multiple sequence alignment by antipole clustering and linear approximate 1-median computation'. Together they form a unique fingerprint.

Cite this