MAGMA: An algorithm for mining multi-level patterns in genomic data

Winnie W M Lam, Chun Chung Chan, David K Y Chiu, Andrew K C Wong

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)

Abstract

Genome comparison is very useful for deriving evolutionary and functional relationships between genomes. Previous works on genome comparison focus mainly on comparing the entire genome at the nucleotide level. As interesting patterns exist also at the gene and segment level, we propose an algorithm called Multi-Level Genome Comparison Algorithm (MGC) that can allow genome comparison to be performed at multi-level while sequential and regional consistency of gene segments can be determined. Different genomes may have common sub-sequences that differ with each other due to processes such as mutations, lateral transfers, gene rearrangements that cannot be easily identified. The result is that not all the genes can form a certain one-to-one matching gene pair. One-to-many or many-to-many ambiguity relationships may exist. MGC takes this ambiguity into consideration and represents genomes with a new graph representation known as Multi-Level Attributed Graph Mining Algorithm (MAGMA). We tested MGC with the intra- and inter-species of Chlamydia genomes. The results show that the proposed algorithm is able to discover the similarities and dissimilarities among different genomes, while in addition, to confirm the specific role of the gene in the genomes and provide variations among species and similarity within species.
Original languageEnglish
Title of host publicationProceedings - 2007 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2007
Pages89-94
Number of pages6
DOIs
Publication statusPublished - 1 Dec 2007
Event2007 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2007 - Fremont, CA, United States
Duration: 2 Nov 20074 Nov 2007

Conference

Conference2007 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2007
CountryUnited States
CityFremont, CA
Period2/11/074/11/07

Keywords

  • Consistency
  • Genome comparison
  • Graph
  • Multi-level
  • Segment

ASJC Scopus subject areas

  • Biotechnology
  • Computer Science(all)
  • Biomedical Engineering

Cite this