Sage Journals: Discover world-class research

Abstract

Multiple sequence alignment is one of the important research topics in computational biology and is widely used in the field of DNA and protein analysis. On the one hand, when the number and length of the sequences are increased when developing copy-number variant (CNV) and Single Nucleotide Polymorphisms (SNP), the multiple sequence alignment becomes very complicated and difficult; on the other hand, the accuracy of the sequence alignment directly influences the results of DNA or protein analysis. In this paper, a novel algorithm for multiple sequence alignment based on center star alignment and MapReduce framework is proposed. The algorithm adapts improved star align strategy so as to work accurately and makes full use of the specialties of data analysis in MapReduce when assembling center sequence and matching the maximum sub strings of two sequences. Experimental results show that the proposed algorithm has better accuracy than other existing algorithms and can relatively quickly align multiple sequences.

Keywords

Multiple sequence alignment center star alignment MapReduce

Get full access to this article

View all access options for this article.

References

Zou

Shan

and Jiang

, A novel center star multiple sequence alignment algorithm based on affine gap penalty and K-band, Physics Procedia (33) (2012), 322–327.

Zou

Guo

Wang

and Zhang

, An algorithm for dna multiple sequence alignment based on center star method and keyword tree, Acta Electronica Sinica (37) (2009), 1746–1750.

Jonathan

M.K.

Peter

and Darryn

, A simulated annealing algorithm for finding consensus sequences, Bioinformatics (18) (2002), 1494–1499.

Lee

Z.J.

S.F.

Chuang

C.C.

and Liu

K.H.

, Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment, Applied Soft Computing (8) (2008), 55–78.

Kaya

Sarhan

and Alhajj

, Multiple sequence alignment with affine gap by using multi-objective genetic algorithm, Comput Methods Programs Biomed (114) (2014), 38–49.

Schwartz

A.S.

and Pachter

, Multiple alignment by sequence annealing, Bioinformatics (23) (2007), e24–e29.

Orobitg

Cores

Guirado

Roig

and Notredame

, Improving multiple sequence alignment biological accuracy through genetic algorithms, The Journal of Supercomputing (65) (2013), 1076–1088.

Narimani

and Hamid

, A new genetic algorithm for multiple sequence alignment, International Journal of Computational Intelligence and Applications (11) (2012), 1.

Löytynoja

Vilella

A.J.

and Goldman

, Accurate extension of multiple sequence alignments using a phylogeny-aware graph algorithm, Bioinformatics (28) (2012), 1684–1691.

10.

Chen

Liao

Zhu

and Xiang

, Multiple sequence alignment algorithm based on a dispersion graph and ant colony algorithm, Journal of Computational Chemistry (30) (2009), 2031–2038.

11.

Katoh

and Standley

D.M.

, MAFFT Multiple Sequence Alignment Software Version 7: Improvements in Performance and Usability, Molecular Biology And Evolution. 30(4) (2013), 772–780.

12.

Notredame

Higgins

D.G.

and Heringa

, T-Coffee: A novel method for fast and accurate multiple sequence alignment, Journal of Molecular Biology. (302) (2000), 205–217.

13.

Higgins

Bleasby

and Fuchs

, CLUSTAL V: Using clustal for multiple sequence alignment, Comput Appl.Biosci. (8) (1992), 189–191.

14.

Thomposon

J.D.

Gibson

T.J.

and Higgins

, CLUSTALW: improving the sensitivity of progressive multiple sequence alignment through sequence weighting position-specific gap penalties and weight matrix choice, Nucleic Acids Research (22) (1994), 4673–4680.

15.

Lalwani

Kumar

and Gupta

, A novel two-level particle swarm optimization approach for efficient multiple sequence alignment, Memetic Computing (7) (2015), 119–133.

16.

Blazewicz

Frohmberg

Kierzynka

and Wojciechowski

, MSA – A GPU-based, fast and accurate algorithm for multiple sequence alignment, Journal of Parallel and Distributed Computing (73) (2013), 32–41.

17.

Sievers

Dineen

Wilm

and Higgins

D.G.

, Making automated multiple alignments of very large numbers of protein sequences, Bioinformatics (29) (2013), 989–995.

18.

Boyce

Sievers

and Higgins

D.G.

, Simple chained guide trees give high-quality protein multiple sequence alignments, in: Proceedings of the National Academy of Science of the United States of America (111) (2014), 10556–10561.

19.

Shu

Elofsson

and Kalign

, Improved multiple sequence alignments using position specific gap penalties in Kalign2, Bioinformatics (2011), 27.

20.

Zou

Guo

and Wang

, HAlign: Fast multiple similar DNA/RNA sequence alignment based on the centre star strategy, Bioinformatics 31(15) (2015), 2475–2481.

21.

Chen

Wang

and Tang

, CMSA: a heterogeneous CPU/GPU computing system for multiple similar RNA/DNA sequence alignment, BMC Bioinformatics 18(1) (2017), 315.

22.

Zhou

, Research on parallel algorithm of multiple DNA sequence alignment based on de bruijn graph, Nature Biotechnology (2010).

23.

Compeau

P.E.

Pevzner

P.A.

and Tesler

, How to apply de Bruijn graphs to genome assembly, Nature Biotechnology (29) (2011), 987–991.

An accurate algorithm for multiple sequence alignment in MapReduce

Abstract

Keywords

Get full access to this article

References