ASSIRC: Accelerated Search for Similar Regions in Chromosomes

• An algorithm in three steps :

  • Identification of pairs of common patterns of fixed size k (seeds).
  • Extension of the seeds to determine the limits of the putative pairs of regions of similarity by a random walk procedure.
  • Final validation of pairs by alignment.

• The pairs of regions are recorded by :

  • using the Red-Black Tree structure (for rapid access).
  • joining adjacent pairs together (to take gaps into account).