Bioinformatics Advance Access originally published online on July 12, 2006
Bioinformatics 2006 22(18):2196-2203; doi:10.1093/bioinformatics/btl369
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
© 2006 The Author(s)
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/2.0/uk/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Interpolated variable order motifs for identification of horizontally acquired DNA: revisiting the Salmonella pathogenicity islands
The Wellcome Trust Sanger Institute, Wellcome Trust Genome Campus Hinxton, Cambridge CB10 1SA, UK
*To whom correspondence should be addressed.
Motivation: There is a growing literature on the detection of Horizontal Gene Transfer (HGT) events by means of parametric, non-comparative methods. Such approaches rely only on sequence information and utilize different low and high order indices to capture compositional deviation from the genome backbone; the superiority of the latter over the former has been shown elsewhere. However even high order k-mers may be poor estimators of HGT, when insufficient information is available, e.g. in short sliding windows. Most of the current HGT prediction methods require pre-existing annotation, which may restrict their application on newly sequenced genomes.
Results: We introduce a novel computational method, Interpolated Variable Order Motifs (IVOMs), which exploits compositional biases using variable order motif distributions and captures more reliably the local composition of a sequence compared with fixed-order methods. For optimal localization of the boundaries of each predicted region, a second order, two-state hidden Markov model (HMM) is implemented in a change-point detection framework. We applied the IVOM approach to the genome of Salmonella enterica serovar Typhi CT18, a well-studied prokaryote in terms of HGT events, and we show that the IVOMs outperform state-of-the-art low and high order motif methods predicting not only the already characterized Salmonella Pathogenicity Islands (SPI-1 to SPI-10) but also three novel SPIs (SPI-15, SPI-16, SPI-17) and other HGT events.
Availability: The software is available under a GPL license as a standalone application at http://www.sanger.ac.uk/Software/analysis/alien_hunter
Contact: gsv{at}sanger.ac.uk
Supplementary Information: Supplementary data are available at Bioinformatics online.
Received on May 3, 2006; revised on June 22, 2006; accepted on July 3, 2006
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  A. J. Arvey, R. K. Azad, A. Raval, and J. G. Lawrence Detection of genomic islands via segmental genome heterogeneity Nucleic Acids Res., September 1, 2009; 37(16): 5255 - 5266. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. R. Wattam, K. P. Williams, E. E. Snyder, N. F. Almeida Jr., M. Shukla, A. W. Dickerman, O. R. Crasta, R. Kenyon, J. Lu, J. M. Shallom, et al. Analysis of Ten Brucella Genomes Reveals Evidence for Horizontal Gene Transfer Despite a Preferred Intracellular Lifestyle J. Bacteriol., June 1, 2009; 191(11): 3569 - 3579. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. J. Croucher, D. Walker, P. Romero, N. Lennard, G. K. Paterson, N. C. Bason, A. M. Mitchell, M. A. Quail, P. W. Andrew, J. Parkhill, et al. Role of Conjugative Elements in the Evolution of the Multidrug-Resistant Pandemic Clone Streptococcus pneumoniaeSpain23F ST81 J. Bacteriol., March 1, 2009; 191(5): 1480 - 1489. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. G. I. Langille and F. S. L. Brinkman IslandViewer: an integrated interface for computational identification and visualization of genomic islands Bioinformatics, March 1, 2009; 25(5): 664 - 665. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Winstanley, M. G.I. Langille, J. L. Fothergill, I. Kukavica-Ibrulj, C. Paradis-Bleau, F. Sanschagrin, N. R. Thomson, G. L. Winsor, M. A. Quail, N. Lennard, et al. Newly introduced genomic prophage islands are critical determinants of in vivo competitiveness in the Liverpool Epidemic Strain of Pseudomonas aeruginosa Genome Res., January 1, 2009; 19(1): 12 - 23. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. R. Thomson, D. J. Clayton, D. Windhorst, G. Vernikos, S. Davidson, C. Churcher, M. A. Quail, M. Stevens, M. A. Jones, M. Watson, et al. Comparative genome analysis of Salmonella Enteritidis PT4 and Salmonella Gallinarum 287/91 provides insights into evolutionary and host adaptation pathways Genome Res., October 1, 2008; 18(10): 1624 - 1637. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Letek, A. A. Ocampo-Sosa, M. Sanders, U. Fogarty, T. Buckley, D. P. Leadon, P. Gonzalez, M. Scortti, W. G. Meijer, J. Parkhill, et al. Evolution of the Rhodococcus equi vap Pathogenicity Island Seen through Comparison of Host-Associated vapA and vapB Virulence Plasmids J. Bacteriol., September 1, 2008; 190(17): 5797 - 5805. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. M. Buboltz, T. L. Nicholson, M. R. Parette, S. E. Hester, J. Parkhill, and E. T. Harvill Replacement of Adenylate Cyclase Toxin in a Lineage of Bordetella bronchiseptica J. Bacteriol., August 1, 2008; 190(15): 5502 - 5511. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. M. Pearson, M. Sebaihia, C. Churcher, M. A. Quail, A. S. Seshasayee, N. M. Luscombe, Z. Abdellah, C. Arrosmith, B. Atkin, T. Chillingworth, et al. Complete Genome Sequence of Uropathogenic Proteus mirabilis, a Master of both Adherence and Motility J. Bacteriol., June 1, 2008; 190(11): 4027 - 4037. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. P. Stinear, T. Seemann, P. F. Harrison, G. A. Jenkin, J. K. Davies, P. D.R. Johnson, Z. Abdellah, C. Arrowsmith, T. Chillingworth, C. Churcher, et al. Insights from the complete genome sequence of Mycobacterium marinum on the evolution of Mycobacterium tuberculosis Genome Res., May 1, 2008; 18(5): 729 - 741. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. D. Saroj, R. Shashidhar, M. Karani, and J. R. Bandekar Distribution of Salmonella pathogenicity island (SPI)-8 and SPI-10 among different serotypes of Salmonella J. Med. Microbiol., April 1, 2008; 57(4): 424 - 427. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
G. S. Vernikos and J. Parkhill Resolving the structural features of genomic islands: A machine learning approach Genome Res., February 1, 2008; 18(2): 331 - 342. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. R. Zaneveld, D. R. Nemergut, and R. Knight Are all horizontal gene transfers created equal? Prospects for mechanism-based studies of HGT patterns Microbiology, January 1, 2008; 154(1): 1 - 15. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. K. Azad and J. G. Lawrence Detecting laterally transferred genes: use of entropic clustering methods and genome position Nucleic Acids Res., July 9, 2007; 35(14): 4629 - 4639. [Abstract] [Full Text] [PDF]
|
|