Complexity and enumeration in models of genome rearrangement

被引：0

作者：

Bailey, Lora ^{[1
]}

Blake, Heather Smith ^{[2
]}

Cochran, Garner ^{[3
]}

Fox, Nathan ^{[4
]}

Levet, Michael ^{[5
]}

Mahmoud, Reem ^{[6
]}

Matson, Elizabeth Bailey ^{[7
]}

Singgih, Inne ^{[8
]}

Stadnyk, Grace ^{[9
]}

Wang, Xinyi ^{[10
]}

Wiedemann, Alexander ^{[11
]}

机构：

[1] Grand Valley State Univ, Dept Math, Allendale, MI USA

[2] Davidson Coll, Dept Math & Comp Sci, Davidson, NC USA

[3] Berry Coll, Dept Math & Comp Sci, Mt Berry, GA USA

[4] Canisius Univ, Dept Quantitat Sci, Buffalo, NY USA

[5] Coll Charleston, Dept Comp Sci, Charleston, SC 29424 USA

[6] NYU Abu Dhabi, Div Sci, Abu Dhabi, U Arab Emirates

[7] Alfred Univ, Div Math & Comp Sci, Alfred, NY USA

[8] Univ Cincinnati, Dept Math Sci, Cincinnati, OH USA

[9] Furman Univ, Dept Math, Greenville, SC USA

[10] Michigan State Univ, Dept Computat Math Sci & Engn, E Lansing, MI USA

[11] Hamline Univ, Dept Math & Computat Data Sci, St Paul, MN USA

来源：

THEORETICAL COMPUTER SCIENCE | 2024年 / 1022卷

基金：

美国国家科学基金会;

关键词：

SINGLE-CUT; PERMUTATIONS; ASSIGNMENT; PERMANENT; CIRCUITS; DISTANCE; SCJ;

D O I：

10.1016/j.tcs.2024.114880

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we examine the computational complexity of enumeration in certain genome rearrangement models. We first show that the PAIRWISE REARRANGEMENT problem in the Single Cut-and-Join model (Bergeron et al., 2010 [8]) is #P-complete under polynomial-time Turing reductions. Next, we show that in the Single Cut or Join model (Feijao and Meidanis, 2011 [21]), the problem of enumerating all medians (#MEDIAN) is logspace-computable (FL), FL), improving upon the previous polynomial-time (FP) bound of Miklos & Smith [41].

引用

页数：17

共 62 条

[1] Ajana Y, 2002, LECT NOTES COMPUT SC, V2452, P300
[2] Comparative genomics reveals birth and death of fragile regions in mammalian evolution
Alekseyev, Max A.
Pevzner, Pavel A.
[J]. GENOME BIOLOGY, 2010, 11 (11):
[3] The permanent requires large uniform threshold circuits
Allender, E
[J]. CHICAGO JOURNAL OF THEORETICAL COMPUTER SCIENCE, 1999, (07): : 1 - 19
[4] Arora S, 2009, COMPUTATIONAL COMPLEXITY: A MODERN APPROACH, P508
[5] Primate segmental duplications: crucibles of evolution, diversity and disease
Bailey, Jeffrey A.
Eichler, Evan E.
[J]. NATURE REVIEWS GENETICS, 2006, 7 (07) : 552 - 564
[6] Bailey Lora, 2024, Computing and Combinatorics, P3, DOI [/10.1007/978-3-031-, DOI 10.1007/978-3-031]
[7] Bergeron A, 2008, LECT N BIOINFORMAT, V5267, P226, DOI 10.1007/978-3-540-87989-3_17
[8] Bergeron A, 2006, LECT NOTES COMPUT SC, V4175, P163
[9] Rearrangement Models and Single-Cut Operations
Bergeron, Anne
Medvedev, Paul
Stoye, Jens
[J]. JOURNAL OF COMPUTATIONAL BIOLOGY, 2010, 17 (09) : 1213 - 1225
[10] Bixby Eliot, 2016, Involve, V9, P41, DOI [/10.2140/involve.2016.9.41, DOI 10.2140/INVOLVE.2016.9.41]

← 1 2 3 4 5 6 7 →