Back to Projects

N-gram genome analysis

Alignment-free detection of genomic islands in bacterial genomes using n-gram language models, Markov chains, and C4.5 (2010).

Overview

This project explored alignment-free identification of genomic islands in bacterial genomes by modeling nucleotide sequences as a “language”. The goal was to distinguish genomic islands vs. the rest of the sequence based on differences in nucleotide composition and local n-gram patterns.

  • Year: 2010
  • Status: internal research (not published), no public repository
  • Domain: bacterial genomics, sequence segmentation / classification

Alignment-free genomic island detection in bacterial genomes using k-mer (n-gram) language models, Markov chains, and C4.5 for region classification (2010).

Approach

We treated DNA as a sequence over the alphabet {A, C, G, T} and used:

  • n-gram language models (k-mers) to capture local composition
  • Markov chain models to estimate transition structure / likelihoods
  • C4.5 decision tree for supervised classification of windows/regions

Typical workflow:

  1. Windowing/segmentation of genome into fixed-length or sliding windows
  2. Feature extraction from each window
    • n-gram frequency profiles (optionally normalized)
    • Markov-based scores (e.g., likelihood under background vs. island model)
  3. Classification (C4.5) to label windows/regions as island vs. non-island
  4. Post-processing to merge consecutive windows into candidate islands

Notes on signals (intuition)

Genomic islands often differ from the host genome due to horizontal transfer, so they may show:

  • shifts in k-mer distribution
  • changes in transition probabilities between nucleotides
  • detectable boundaries when comparing local (island) statistics vs. genome-wide baseline