TransposonAnnotation

Transposon detection and clustering algorithms

• Bergman CM, Quesneville H.  Discovering and detecting transposable elements in genome sequences.  Brief Bioinform. 2007 Nov;8(6):382-92. Epub 2007 Oct 10.
  • Review of computational methods to study transposable elements in genomes
  • An up-to-date compendium of TE bioinformatics tools from this review can be found here

• Caspi A, Pachter L.  Identification of transposable elements using multiple alignments of related genomes.  Genome Res. 2006 Feb;16(2):260-70. Epub 2005 Dec 14.
  • Transposons are identifiable as big insertions in multi-genome alignments

• Bao Z, Eddy SR.  Automated de novo identification of repeat sequence families in sequenced genomes.  Genome Res. 2002 Aug;12(8):1269-76.
  • Transposon boundaries correspond to sharp changes in the density of BLAST hits

• Bejerano G, Haussler D, Blanchette M.  Into the heart of darkness: large-scale clustering of human non-coding DNA.  Bioinformatics. 2004 Aug 4;20 Suppl 1:i40-8.
  • Start with a graph whose nodes are all putative transposons & edges correspond to BLAST matches
  • Apply the following heuristic to break up this graph:
    • Split any node whose set of neighbors can be partitioned into two dissimilar subsets
    • Iterate, reducing graph to a set of densely-connected subgraphs

• Edgar RC, Myers EW.  PILER: identification and classification of genomic repeats.  Bioinformatics. 2005 Jun;21 Suppl 1:i152-8.
  • Edgar: an "intact instance" of a transposon has multiple BLAST hits sharing exact same coords (i.e. remote homologues that are globally alignable)

• Andrieu O, Fiston AS, Anxolabehere D, Quesneville H.  Detection of transposable elements by their compositional bias.  BMC Bioinformatics. 2004 Jul 13;5:94.
  • Nucleotide composition
  • c.f. irreversible substitution models: Hamady M, Betterton MD, Knight R.  Using the nucleotide substitution rate matrix to detect horizontal gene transfer.  BMC Bioinformatics. 2006 Oct 26;7:476.

• Quesneville H, Bergman CM, Andrieu O, Autard D, Nouaud D, Ashburner M, Anxolabehere D.  Combined evidence annotation of transposable elements in genome sequences.  PLoS Comput Biol. 2005 Jul;1(2):166-75. Epub 2005 Jul 29.
  • Combining multiple lines of evidence

• Li R et al.  ReAS: Recovery of ancestral sequences for transposable elements from the unassembled reads of a whole genome shotgun.  PLoS Comput Biol. 2005 Sep;1(4):e43. Epub 2005 Sep 23.
  • Transposon prediction directly from shotgun reads

• Rho M, Choi JH, Kim S, Lynch M, Tang H.  De novo identification of LTR retrotransposons in eukaryotic genomes.  BMC Genomics. 2007 Apr 3;8:90.
  • LTR transposon identification

Repeats, copy languages and computational linguistics

• McCarthy EM, McDonald JF.  LTR_STRUC: a novel search and identification program for LTR retrotransposons.  Bioinformatics. 2003 Feb 12;19(3):362-7.
  • Profiling LTR transposons

• Mildly context-sensitive grammar formalisms (Kallmeyer, course notes)
  • Tree-adjoining grammars (Joshi and Schabes, 1997)
  • Context-sensitive HMMs (Yoon and Vaidyanathan)

• Conditional random fields (Hanna Wallach) (PDF)
  • Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data (Lafferty, McCallum and Pereira)
  • Sato K, Sakakibara Y.  RNA secondary structural alignment with conditional random fields.  Bioinformatics. 2005 Sep 1;21 Suppl 2:ii237-42.
  • Repetitive element segmentation and homology assignment (Anat Caspi, 2005)