Multiple genome alignment by clustering pairwise matches

Jeong Hyeon Choi, Kwangmin Choi, Hwan Gue Cho, Sun Kim

Research output: Contribution to journalConference articlepeer-review

6 Scopus citations

Abstract

We have developed a multiple genome alignment algorithm by using a sequence clustering algorithm to combine local pairwise genome sequence matches produced by pairwise genome alignments, e.g, BLASTZ. Sequence clustering algorithms often generate clusters of sequences such that there exists a common shared region among all sequences in each cluster. To use a sequence clustering algorithm for genome alignment, it is necessary to handle numerous local alignments between a pair of genomes. We propose a multiple genome alignment method that converts the multiple genome alignment problem to the sequence clustering problem. This method does not need to make a guide tree to determine the order of multiple alignment, and it accurately detects multiple homologous regions. As a result, our multiple genome alignment algorithm performs competitively over existing algorithms. This is shown using an experiment which compares the performance of TBA, MultiPipMaker (MPM) and our algorithm in aligning 12 groups of 56 microbial genomes and by evaluating the number of common COGs detected.

Original languageEnglish (US)
Pages (from-to)30-41
Number of pages12
JournalLecture Notes in Bioinformatics (Subseries of Lecture Notes in Computer Science)
Volume3388
DOIs
StatePublished - 2005
Externally publishedYes
EventRECOMB 2004 International Workshop, RRCG 2004 - Comparative Genomics - Bertinoro, Italy
Duration: Oct 16 2004Oct 19 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Multiple genome alignment by clustering pairwise matches'. Together they form a unique fingerprint.

Cite this