title: Alignment-free genetic sequence comparisons: a review of recent approaches by word analysis.
abstract: Modern sequencing and genome assembly technologies have provided a wealth of data, which will soon require an analysis by comparison for discovery. Sequence alignment, a fundamental task in bioinformatics research, may be used but with some caveats. Seminal techniques and methods from dynamic programming are proving ineffective for this work owing to their inherent computational expense when processing large amounts of sequence data. These methods are prone to giving misleading information because of genetic recombination, genetic shuffling and other inherent biological events. New approaches from information theory, frequency analysis and data compression are available and provide powerful alternatives to dynamic programming. These new methods are often preferred, as their algorithms are simpler and are not affected by synteny-related problems. In this review, we provide a detailed discussion of computational tools, which stem from alignment-free methods based on statistical analysis from word frequencies. We provide several clear examples to demonstrate applications and the interpretations over several different areas of alignment-free analysis such as base-base correlations, feature frequency profiles, compositional vectors, an improved string composition and the D2 statistic metric. Additionally, we provide detailed discussion and an example of analysis by Lempel-Ziv techniques from data compression.
authors.forename: Oliver
authors.initials: O
authors.lastname: Bonham-Carter
authors.forename: Joe
authors.initials: J
authors.lastname: Steele
authors.forename: Dhundy
authors.initials: D
authors.lastname: Bastola
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D007257:Information Theory; D058974:Phylogeography; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA / Q000379:methods* / Q000706:statistics & numerical data
keywords: alignment-free; information theory; sequence-alignment; word-analysis
references.citation: Bioinformatics. 2003 Mar 1;19(4):513-23
references.pmid: 12611807
references.citation: Theor Appl Genet. 2012 Feb;124(3):423-32
references.pmid: 22001910
references.citation: Nucleic Acids Res. 2003 Jul 1;31(13):3497-500
references.pmid: 12824352
references.citation: J Comput Biol. 2006 Mar;13(2):336-50
references.pmid: 16597244
references.citation: J Mol Evol. 2005 Apr;60(4):538-45
references.pmid: 15883888
references.citation: J Bioinform Comput Biol. 2004 Mar;2(1):1-19
references.pmid: 15272430
references.citation: Bioinformatics. 2011 Jun 1;27(11):1466-72
references.pmid: 21471011
references.citation: BMC Bioinformatics. 2008 May 28;9 Suppl 6:S15
references.pmid: 18541050
references.citation: Bioinformatics. 2012 Oct 1;28(19):2527-9
references.pmid: 22833526
references.citation: Bioinformatics. 2007 Nov 1;23(21):2947-8
references.pmid: 17846036
references.citation: J Comput Biol. 2013 Feb;20(2):64-79
references.pmid: 23383994
references.citation: Stat Appl Genet Mol Biol. 2009;8:Article 43
references.pmid: 19883369
references.citation: BMC Evol Biol. 2011 Oct 19;11:308
references.pmid: 22011259
references.citation: BMC Bioinformatics. 2013;14 Suppl 11:S5
references.pmid: 24564274
references.citation: Brief Bioinform. 2010 Sep;11(5):473-83
references.pmid: 20460430
references.citation: Annu Rev Genet. 2012;46:341-58
references.pmid: 22934638
references.citation: BMC Res Notes. 2008 Feb 28;1:5
references.pmid: 18710530
references.citation: Bioinformatics. 2004 Nov 22;20(17):3156-65
references.pmid: 15217808
references.citation: Bioinformatics. 1999 Apr;15(4):265-6
references.pmid: 10438229
references.citation: Bioinformatics. 2003 Nov 1;19(16):2122-30
references.pmid: 14594718
references.citation: J Comput Biol. 2010 Nov;17(11):1467-90
references.pmid: 20973742
references.citation: J Mol Evol. 2004 Jan;58(1):1-11
references.pmid: 14743310
references.citation: Proc Natl Acad Sci U S A. 2009 Feb 24;106(8):2677-82
references.pmid: 19188606
references.citation: Bioinformatics. 2007 Jul 1;23(13):i249-55
references.pmid: 17646303
references.citation: Mol Biol Evol. 2008 Sep;25(9):1795-808
references.pmid: 18453548
references.citation: J Mol Biol. 1970 Mar;48(3):443-53
references.pmid: 5420325
references.citation: Mob Genet Elements. 2011 Sep;1(3):230-235
references.pmid: 22312592
references.citation: Int J Bioinform Res Appl. 2006;2(3):219-48
references.pmid: 18048163
references.citation: Bioinformatics. 2005 Nov 15;21(22):4125-32
references.pmid: 16144805
references.citation: Biometrics. 1989 Mar;45(1):35-52
references.pmid: 2720059
references.citation: J Comput Biol. 2011 Mar;18(3):401-13
references.pmid: 21385043
references.citation: Int J Evol Biol. 2011 Mar 03;2011:781642
references.pmid: 21461370
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2012 Jan-Feb;9(1):79-87
references.pmid: 21383416
references.citation: Nat Rev Genet. 2010 Sep;11(9):647-57
references.pmid: 20717155
references.citation: BMC Bioinformatics. 2006 Dec 18;7 Suppl 5:S21
references.pmid: 17254306
references.citation: Proc Natl Acad Sci U S A. 2002 Oct 29;99(22):13980-9
references.pmid: 12374863
references.citation: Genome Res. 2002 Apr;12(4):656-64
references.pmid: 11932250
references.citation: Bioinformatics. 2012 Jun 1;28(11):1415-9
references.pmid: 22556365
references.citation: Nucleic Acids Res. 1997 Sep 1;25(17):3389-402
references.pmid: 9254694
references.citation: J Mol Biol. 1981 Mar 25;147(1):195-7
references.pmid: 7265238
references.citation: J Biomol Struct Dyn. 1986 Aug;4(1):11-21
references.pmid: 3078230
references.citation: Nat Biotechnol. 2004 Jul;22(7):909-10
references.pmid: 15229554
references.citation: Nature. 1998 Jan 15;391(6664):288-91
references.pmid: 9440693
references.citation: J Theor Biol. 2011 Sep 7;284(1):106-16
references.pmid: 21723298
references.citation: ScientificWorldJournal. 2012;2012:450124
references.pmid: 22997494
references.citation: PLoS One. 2011;6(11):e26779
references.pmid: 22102867
references.citation: J Comput Biol. 1999 Fall-Winter;6(3-4):459-74
references.pmid: 10582579
references.citation: J Comput Biol. 2009 Dec;16(12):1615-34
references.pmid: 20001252
references.citation: IEEE Trans Nanobioscience. 2012 Jun;11(2):100-10
references.pmid: 22665391
references.citation: Biochem Biophys Res Commun. 2008 Apr 4;368(2):223-30
references.pmid: 18230342
references.citation: Bioinformatics. 2010 Aug 1;26(15):1899-900
references.pmid: 20427515