Fixed Topology Alignment with Recombination

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

3 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching
Subtitle of host publication9th Annual Symposium, CPM 1998, Proceedings
EditorsMartin Farach-Colton
PublisherSpringer Verlag
Pages174-188
ISBN (Print)3540647392, 9783540647393
Publication statusPublished - Jul 1998

Publication series

NameLecture Notes in Computer Science
Volume1448
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title9th Annual Symposium on Combinatorial Pattern Matching (CPM 1998)
PlaceUnited States
CityPiscataway
Period20 - 22 July 1998

Abstract

In this paper, we study a new version of multiple sequence alignment, fixed topology alignment with recombination. We show that it can not be approximated within any constant ratio unless P-NP. For a more restricted version, we show that the problem is MAX-SNP-hard. This implies that there is no PTAS for this version unless P = NP. We also propose approximation algorithms for a special case, where each internal node has at most one recombination child and any two merge paths for different recombination nodes do not share any common node.

Citation Format(s)

Fixed Topology Alignment with Recombination. / Ma, Bin; Wang, Lusheng; Li, Ming.

Combinatorial Pattern Matching: 9th Annual Symposium, CPM 1998, Proceedings. ed. / Martin Farach-Colton. Springer Verlag, 1998. p. 174-188 (Lecture Notes in Computer Science; Vol. 1448).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review