A parameterized algorithm for (1,2)-exemplar breakpoint distance

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationProceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine
PublisherInstitute of Electrical and Electronics Engineers, Inc.
Pages11-16
ISBN (electronic)9781479956692
Publication statusPublished - Nov 2014

Conference

Title2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014
PlaceUnited Kingdom
CityBelfast
Period2 - 5 November 2014

Abstract

The exemplar breakpoint distance problem is motivated by finding conserved sets of genes between two genomes. It asks to find respective exemplars in two genomes to minimize the breakpoint distance between them. If one genome has no repeated gene (called trivial genome) and the other has genes repeating at most twice, it is referred to as the (1,2)-exemplar breakpoint distance problem, EBD(1, 2) for short. Whether there exists a fixed parameter algorithm for this problem has been open for many years. In this paper, we propose the first fixed parameter algorithm for EBD(1,2). Using a dynamic programming approach, we design an algorithm to solve EBD(1,2) with running time O(4sn2) and space O(4sn), respectively, where n is the number of gene families, and s is the maximum number of genes (minus 1) located between two copies of a gene family in the second genome. Our algorithm can also be used to compute the maximum adjacencies between two genomes. Simulations on real data have verified the effectiveness of our algorithm. The algorithm has been implemented in C++. The software package is available upon request.

Research Area(s)

  • Algorithm, Breakpoint, Exemplar, Genome, Span

Citation Format(s)

A parameterized algorithm for (1,2)-exemplar breakpoint distance. / Wei, Zhexue; Zhu, Daming; Wang, Lusheng.
Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine. Institute of Electrical and Electronics Engineers, Inc., 2014. p. 11-16.

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review