The parameterized complexity of the shared center problem

Zhi-Zhong Chen; Lusheng Wang; Wenji Ma

doi:10.1007/978-3-642-31265-6_35

The parameterized complexity of the shared center problem

Zhi-Zhong Chen
, Lusheng Wang
, Wenji Ma

Department of Computer Science

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

Abstract

Recently, the shared center (SC) problem has been proposed as a mathematical model for inferring the allele-sharing status of a given set of individuals using a database of confirmed haplotypes as reference. The problem was proved to be NP-complete and a ratio-2 polynomial-time approximation algorithm was designed for its minimization version (called the closest shared center (CSC) problem). In this paper, we consider the parameterized complexity of the SC problem. First, we show that the SC problem is W[1]-hard with parameters d and n, where d and n are the radius and the number of (diseased or normal) individuals in the input, respectively. Then, we present two asymptotically optimal parameterized algorithms for the problem. © 2012 Springer-Verlag.

Original language	English
Title of host publication	Combinatorial Pattern Matching
Subtitle of host publication	23rd Annual Symposium, CPM 2012, Proceedings
Publisher	Springer Verlag
Pages	439-452
Volume	7354 LNCS
ISBN (Print)	9783642312649
DOIs	https://doi.org/10.1007/978-3-642-31265-6_35
Publication status	Published - 2012
Event	23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012 - Helsinki, Finland Duration: 3 Jul 2012 → 5 Jul 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7354 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012
Place	Finland
City	Helsinki
Period	3/07/12 → 5/07/12

Research Keywords

allele-sharing status
Haplotype inference
linkage analysis
parameterized algorithms
parameterized complexity
pedigree

Access Output

10.1007/978-3-642-31265-6_35

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Chen, Z.-Z., Wang, L., & Ma, W. (2012). The parameterized complexity of the shared center problem. In Combinatorial Pattern Matching: 23rd Annual Symposium, CPM 2012, Proceedings (Vol. 7354 LNCS, pp. 439-452). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7354 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-31265-6_35

Chen, Zhi-Zhong ; Wang, Lusheng ; Ma, Wenji. / The parameterized complexity of the shared center problem. Combinatorial Pattern Matching: 23rd Annual Symposium, CPM 2012, Proceedings. Vol. 7354 LNCS Springer Verlag, 2012. pp. 439-452 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b52714f16c5e48259042f8c688544056,

title = "The parameterized complexity of the shared center problem",

abstract = "Recently, the shared center (SC) problem has been proposed as a mathematical model for inferring the allele-sharing status of a given set of individuals using a database of confirmed haplotypes as reference. The problem was proved to be NP-complete and a ratio-2 polynomial-time approximation algorithm was designed for its minimization version (called the closest shared center (CSC) problem). In this paper, we consider the parameterized complexity of the SC problem. First, we show that the SC problem is W[1]-hard with parameters d and n, where d and n are the radius and the number of (diseased or normal) individuals in the input, respectively. Then, we present two asymptotically optimal parameterized algorithms for the problem. {\textcopyright} 2012 Springer-Verlag.",

keywords = "allele-sharing status, Haplotype inference, linkage analysis, parameterized algorithms, parameterized complexity, pedigree",

author = "Zhi-Zhong Chen and Lusheng Wang and Wenji Ma",

year = "2012",

doi = "10.1007/978-3-642-31265-6\_35",

language = "English",

isbn = "9783642312649",

volume = "7354 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "439--452",

booktitle = "Combinatorial Pattern Matching",

address = "Germany",

note = "23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012 ; Conference date: 03-07-2012 Through 05-07-2012",

}

Chen, Z-Z, Wang, L & Ma, W 2012, The parameterized complexity of the shared center problem. in Combinatorial Pattern Matching: 23rd Annual Symposium, CPM 2012, Proceedings. vol. 7354 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7354 LNCS, Springer Verlag, pp. 439-452, 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, Helsinki, Finland, 3/07/12. https://doi.org/10.1007/978-3-642-31265-6_35

The parameterized complexity of the shared center problem. / Chen, Zhi-Zhong; Wang, Lusheng; Ma, Wenji.
Combinatorial Pattern Matching: 23rd Annual Symposium, CPM 2012, Proceedings. Vol. 7354 LNCS Springer Verlag, 2012. p. 439-452 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7354 LNCS).

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

TY - GEN

T1 - The parameterized complexity of the shared center problem

AU - Chen, Zhi-Zhong

AU - Wang, Lusheng

AU - Ma, Wenji

PY - 2012

Y1 - 2012

N2 - Recently, the shared center (SC) problem has been proposed as a mathematical model for inferring the allele-sharing status of a given set of individuals using a database of confirmed haplotypes as reference. The problem was proved to be NP-complete and a ratio-2 polynomial-time approximation algorithm was designed for its minimization version (called the closest shared center (CSC) problem). In this paper, we consider the parameterized complexity of the SC problem. First, we show that the SC problem is W[1]-hard with parameters d and n, where d and n are the radius and the number of (diseased or normal) individuals in the input, respectively. Then, we present two asymptotically optimal parameterized algorithms for the problem. © 2012 Springer-Verlag.

AB - Recently, the shared center (SC) problem has been proposed as a mathematical model for inferring the allele-sharing status of a given set of individuals using a database of confirmed haplotypes as reference. The problem was proved to be NP-complete and a ratio-2 polynomial-time approximation algorithm was designed for its minimization version (called the closest shared center (CSC) problem). In this paper, we consider the parameterized complexity of the SC problem. First, we show that the SC problem is W[1]-hard with parameters d and n, where d and n are the radius and the number of (diseased or normal) individuals in the input, respectively. Then, we present two asymptotically optimal parameterized algorithms for the problem. © 2012 Springer-Verlag.

KW - allele-sharing status

KW - Haplotype inference

KW - linkage analysis

KW - parameterized algorithms

KW - parameterized complexity

KW - pedigree

UR - https://www.scopus.com/pages/publications/84863112950

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84863112950&origin=recordpage

U2 - 10.1007/978-3-642-31265-6_35

DO - 10.1007/978-3-642-31265-6_35

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783642312649

VL - 7354 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 439

EP - 452

BT - Combinatorial Pattern Matching

PB - Springer Verlag

T2 - 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012

Y2 - 3 July 2012 through 5 July 2012

ER -

Chen ZZ, Wang L, Ma W. The parameterized complexity of the shared center problem. In Combinatorial Pattern Matching: 23rd Annual Symposium, CPM 2012, Proceedings. Vol. 7354 LNCS. Springer Verlag. 2012. p. 439-452. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-31265-6_35

The parameterized complexity of the shared center problem

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this