title: Alignment-free sequence comparison based on next-generation sequencing reads.
abstract: Next-generation sequencing (NGS) technologies have generated enormous amounts of shotgun read data, and assembly of the reads can be challenging, especially for organisms without template sequences. We study the power of genome comparison based on shotgun read data without assembly using three alignment-free sequence comparison statistics, D(2), D(*)(2) and D(s)(2), both theoretically and by simulations. Theoretical formulas for the power of detecting the relationship between two sequences related through a common motif model are derived. It is shown that both D(*)(2) and D(s)(2), outperform D(2) for detecting the relationship between two sequences based on NGS data. We then study the effects of length of the tuple, read length, coverage, and sequencing error on the power of D(*)(2) and D(s)(2). Finally, variations of these statistics, d(2), d(*)(2) and d(s)(2), respectively, are used to first cluster five mammalian species with known phylogenetic relationships, and then cluster 13 tree species whose complete genome sequences are not available using NGS shotgun reads. The clustering results using d(s)(2) are consistent with biological knowledge for the 5 mammalian and 13 tree species, respectively. Thus, the statistic d(s)(2) provides a powerful alignment-free comparison tool to study the relationships among different organisms based on NGS read data without assembly.
authors: School of Mathematics, Peking University, Beijing, PR China.
authors: Kai
authors: K
authors: Song
authors: Jie
authors: J
authors: Ren
authors: Zhiyuan
authors: Z
authors: Zhai
authors: Xuemei
authors: X
authors: Liu
authors: Minghua
authors: M
authors: Deng
authors: Fengzhu
authors: F
authors: Sun
mesh_terms: D000465:Algorithms; D000818:Animals; D001482:Base Composition; D002645:Chickens / Q000235:genetics; D016000:Cluster Analysis; D003198:Computer Simulation; D016678:Genome; D059014:High-Throughput Nucleotide Sequencing; D006801:Humans; D051379:Mice; D008957:Models, Genetic; D009893:Opossums / Q000235:genetics; D010802:Phylogeny; D011817:Rabbits; D017422:Sequence Analysis, DNA / Q000379:methods / Q000706:statistics & numerical data*; D014197:Trees / Q000145:classification / Q000235:genetics
references: Genome Res. 2007 Dec;17(12):1797-808
references: 17984227
references: Genome Biol. 2008 Jan 28;9(1):R22
references: 18226245
references: Genome Biol. 2010;11(5):R50
references: 20459815
references: PLoS One. 2009 Sep 04;4(9):e6901
references: 19730735
references: J Comput Biol. 2010 Nov;17(11):1467-90
references: 20973742
references: Proc Natl Acad Sci U S A. 2009 Feb 24;106(8):2677-82
references: 19188606
references: Proc Natl Acad Sci U S A. 2002 Oct 29;99(22):13980-9
references: 12374863
references: J Theor Biol. 2011 Sep 7;284(1):106-16
references: 21723298
references: PLoS Comput Biol. 2008 Aug 22;4(8):e1000158
references: 18725927
references: J Comput Biol. 2009 Dec;16(12):1615-34
references: 20001252
references: Bioinformatics. 2011 Jun 1;27(11):1466-72
references: 21471011
references: PLoS One. 2008 Oct 08;3(10):e3373
references: 18841204
references: Mol Ecol. 2010 Mar;19 Suppl 1:147-61
references: 20331777
references: Bioinformatics. 2003 Mar 1;19(4):513-23
references: 12611807
references: Proc Natl Acad Sci U S A. 2010 Jan 5;107(1):133-8
references: 20018669
references: J Comput Biol. 2010 Apr;17(4):581-92
references: 20426691
references: Nucleic Acids Res. 2010 Jul;38(12):e131
references: 20395217
references: Proc Natl Acad Sci U S A. 1986 Jul;83(14):5155-9
references: 3460087