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

doi:10.1109/CSB.2003.1227333

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 proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	326-336
Number of pages	11
ISBN (Electronic)	0769520006, 9780769520001
DOIs	https://doi.org/10.1109/CSB.2003.1227333
State	Published - 2003
Event	2nd International IEEE Computer Society Computational Systems Bioinformatics Conference, CSB 2003 - Stanford, United States Duration: Aug 11 2003 → Aug 14 2003

Publication series

Name	Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003

Other

Other	2nd International IEEE Computer Society Computational Systems Bioinformatics Conference, CSB 2003
Country/Territory	United States
City	Stanford
Period	8/11/03 → 8/14/03

Keywords

Clustering
Multiple Sequence Alignment
Randomized Tournament

ASJC Scopus subject areas

Electrical and Electronic Engineering
Computer Science Applications

Access to Document

10.1109/CSB.2003.1227333

Cite this

Di Pietro, C., Di Pietro, V., Emmanuele, G., Ferro, A., Maugeri, T., Modica, E., Pigola, G., Pulvirenti, A., Purrello, M., Ragusa, M., Scalia, M., Shasha, D., Travali, S., & Zimmitti, V. (2003). Anticlustal: Multiple sequence alignment by antipole clustering and linear approximate 1-median computation. In Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003 (pp. 326-336). Article 1227333 (Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CSB.2003.1227333

Anticlustal: Multiple sequence alignment by antipole clustering and linear approximate 1-median computation. / Di Pietro, C.; Di Pietro, V.; Emmanuele, G. et al.
Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003. Institute of Electrical and Electronics Engineers Inc., 2003. p. 326-336 1227333 (Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Di Pietro, C, Di Pietro, V, Emmanuele, G, Ferro, A, Maugeri, T, Modica, E, Pigola, G, Pulvirenti, A, Purrello, M, Ragusa, M, Scalia, M, Shasha, D, Travali, S & Zimmitti, V 2003, Anticlustal: Multiple sequence alignment by antipole clustering and linear approximate 1-median computation. in Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003., 1227333, Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003, Institute of Electrical and Electronics Engineers Inc., pp. 326-336, 2nd International IEEE Computer Society Computational Systems Bioinformatics Conference, CSB 2003, Stanford, United States, 8/11/03. https://doi.org/10.1109/CSB.2003.1227333

Di Pietro C, Di Pietro V, Emmanuele G, Ferro A, Maugeri T, Modica E et al. Anticlustal: Multiple sequence alignment by antipole clustering and linear approximate 1-median computation. In Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003. Institute of Electrical and Electronics Engineers Inc. 2003. p. 326-336. 1227333. (Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003). doi: 10.1109/CSB.2003.1227333

Di Pietro, C. ; Di Pietro, V. ; Emmanuele, G. et al. / Anticlustal : Multiple sequence alignment by antipole clustering and linear approximate 1-median computation. Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003. Institute of Electrical and Electronics Engineers Inc., 2003. pp. 326-336 (Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003).

@inproceedings{907aaeaf50bb42d380c063d649f50cba,

title = "Anticlustal: Multiple sequence alignment by antipole clustering and linear approximate 1-median computation",

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.",

keywords = "Clustering, Multiple Sequence Alignment, Randomized Tournament",

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

note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 2nd International IEEE Computer Society Computational Systems Bioinformatics Conference, CSB 2003 ; Conference date: 11-08-2003 Through 14-08-2003",

year = "2003",

doi = "10.1109/CSB.2003.1227333",

language = "English (US)",

series = "Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "326--336",

booktitle = "Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003",

}

TY - GEN

T1 - Anticlustal

T2 - 2nd International IEEE Computer Society Computational Systems Bioinformatics Conference, CSB 2003

AU - Di Pietro, C.

AU - Di Pietro, V.

AU - Emmanuele, G.

AU - Ferro, A.

AU - Maugeri, T.

AU - Modica, E.

AU - Pigola, G.

AU - Pulvirenti, A.

AU - Purrello, M.

AU - Ragusa, M.

AU - Scalia, M.

AU - Shasha, D.

AU - Travali, S.

AU - Zimmitti, V.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - Clustering

KW - Multiple Sequence Alignment

KW - Randomized Tournament

UR - http://www.scopus.com/inward/record.url?scp=84960351626&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84960351626&partnerID=8YFLogxK

U2 - 10.1109/CSB.2003.1227333

DO - 10.1109/CSB.2003.1227333

M3 - Conference contribution

C2 - 16452808

AN - SCOPUS:84960351626

T3 - Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003

SP - 326

EP - 336

BT - Proceedings of the 2003 IEEE Bioinformatics Conference, CSB 2003

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 11 August 2003 through 14 August 2003

ER -

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this