---
_id: '14739'
abstract:
- lang: eng
text: Attempts to incorporate topological information in supervised learning tasks
have resulted in the creation of several techniques for vectorizing persistent
homology barcodes. In this paper, we study thirteen such methods. Besides describing
an organizational framework for these methods, we comprehensively benchmark them
against three well-known classification tasks. Surprisingly, we discover that
the best-performing method is a simple vectorization, which consists only of a
few elementary summary statistics. Finally, we provide a convenient web application
which has been designed to facilitate exploration and experimentation with various
vectorization methods.
acknowledgement: "The work of Maria-Jose Jimenez, Eduardo Paluzo-Hidalgo and Manuel
Soriano-Trigueros was supported in part by the Spanish grant Ministerio de Ciencia
e Innovacion under Grants TED2021-129438B-I00 and PID2019-107339GB-I00, and in part
by REXASI-PRO H-EU project, call HORIZON-CL4-2021-HUMAN-01-01 under Grant 101070028.
The work of\r\nMaria-Jose Jimenez was supported by a grant of Convocatoria de la
Universidad de Sevilla para la recualificacion del sistema universitario español,
2021-23, funded by the European Union, NextGenerationEU. The work of Vidit Nanda
was supported in part by EPSRC under Grant EP/R018472/1 and in part by US AFOSR
under Grant FA9550-22-1-0462. \r\nWe are grateful to the team of GUDHI and TEASPOON
developers, for their work and their support. We are also grateful to Streamlit
for providing extra resources to deploy the web app\r\nonline on Streamlit community
cloud. We thank the anonymous referees for their helpful suggestions."
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Dashti
full_name: Ali, Dashti
last_name: Ali
- first_name: Aras
full_name: Asaad, Aras
last_name: Asaad
- first_name: Maria-Jose
full_name: Jimenez, Maria-Jose
last_name: Jimenez
- first_name: Vidit
full_name: Nanda, Vidit
last_name: Nanda
- first_name: Eduardo
full_name: Paluzo-Hidalgo, Eduardo
last_name: Paluzo-Hidalgo
- first_name: Manuel
full_name: Soriano Trigueros, Manuel
id: 15ebd7cf-15bf-11ee-aebd-bb4bb5121ea8
last_name: Soriano Trigueros
orcid: 0000-0003-2449-1433
citation:
ama: Ali D, Asaad A, Jimenez M-J, Nanda V, Paluzo-Hidalgo E, Soriano Trigueros M.
A survey of vectorization methods in topological data analysis. IEEE Transactions
on Pattern Analysis and Machine Intelligence. 2023;45(12):14069-14080. doi:10.1109/tpami.2023.3308391
apa: Ali, D., Asaad, A., Jimenez, M.-J., Nanda, V., Paluzo-Hidalgo, E., & Soriano
Trigueros, M. (2023). A survey of vectorization methods in topological data analysis.
IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. https://doi.org/10.1109/tpami.2023.3308391
chicago: Ali, Dashti, Aras Asaad, Maria-Jose Jimenez, Vidit Nanda, Eduardo Paluzo-Hidalgo,
and Manuel Soriano Trigueros. “A Survey of Vectorization Methods in Topological
Data Analysis.” IEEE Transactions on Pattern Analysis and Machine Intelligence.
IEEE, 2023. https://doi.org/10.1109/tpami.2023.3308391.
ieee: D. Ali, A. Asaad, M.-J. Jimenez, V. Nanda, E. Paluzo-Hidalgo, and M. Soriano
Trigueros, “A survey of vectorization methods in topological data analysis,” IEEE
Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 12.
IEEE, pp. 14069–14080, 2023.
ista: Ali D, Asaad A, Jimenez M-J, Nanda V, Paluzo-Hidalgo E, Soriano Trigueros
M. 2023. A survey of vectorization methods in topological data analysis. IEEE
Transactions on Pattern Analysis and Machine Intelligence. 45(12), 14069–14080.
mla: Ali, Dashti, et al. “A Survey of Vectorization Methods in Topological Data
Analysis.” IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 45, no. 12, IEEE, 2023, pp. 14069–80, doi:10.1109/tpami.2023.3308391.
short: D. Ali, A. Asaad, M.-J. Jimenez, V. Nanda, E. Paluzo-Hidalgo, M. Soriano
Trigueros, IEEE Transactions on Pattern Analysis and Machine Intelligence 45 (2023)
14069–14080.
date_created: 2024-01-08T09:59:46Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-08T10:11:46Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1109/tpami.2023.3308391
file:
- access_level: open_access
checksum: 465c28ef0b151b4b1fb47977ed5581ab
content_type: application/pdf
creator: dernst
date_created: 2024-01-08T10:09:14Z
date_updated: 2024-01-08T10:09:14Z
file_id: '14740'
file_name: 2023_IEEEToP_Ali.pdf
file_size: 2370988
relation: main_file
success: 1
file_date_updated: 2024-01-08T10:09:14Z
has_accepted_license: '1'
intvolume: ' 45'
issue: '12'
keyword:
- Applied Mathematics
- Artificial Intelligence
- Computational Theory and Mathematics
- Computer Vision and Pattern Recognition
- Software
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 14069-14080
publication: IEEE Transactions on Pattern Analysis and Machine Intelligence
publication_identifier:
eissn:
- 1939-3539
issn:
- 0162-8828
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: A survey of vectorization methods in topological data analysis
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 45
year: '2023'
...
---
_id: '12164'
abstract:
- lang: eng
text: 'A shared-memory counter is a widely-used and well-studied concurrent object.
It supports two operations: An Inc operation that increases its value by 1 and
a Read operation that returns its current value. In Jayanti et al (SIAM J Comput,
30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case
step complexity of obstruction-free implementations, from read-write registers,
of a large class of shared objects that includes counters. The lower bound leaves
open the question of finding counter implementations with sub-linear amortized
step complexity. In this work, we address this gap. We show that n-process, wait-free
and linearizable counters can be implemented from read-write registers with O(log2n)
amortized step complexity. This is the first counter algorithm from read-write
registers that provides sub-linear amortized step complexity in executions of
arbitrary length. Since a logarithmic lower bound on the amortized step complexity
of obstruction-free counter implementations exists, our upper bound is within
a logarithmic factor of the optimal. The worst-case step complexity of the construction
remains linear, which is optimal. This is obtained thanks to a new max register
construction with O(logn) amortized step complexity in executions of arbitrary
length in which the value stored in the register does not grow too quickly. We
then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel
[1] in which we “plug” our max register implementation to show that it remains
linearizable while achieving O(log2n) amortized step complexity.'
acknowledgement: A preliminary version of this work appeared in DISC’19. Mirza Ahad
Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes
and FREDDA. Mirza Ahad Baig is supported by UMI Relax. Danny Hendler is supported
by the Israel Science Foundation (Grants 380/18 and 1425/22).
article_processing_charge: No
article_type: original
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Danny
full_name: Hendler, Danny
last_name: Hendler
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
- first_name: Corentin
full_name: Travers, Corentin
last_name: Travers
citation:
ama: Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic
amortized step complexity. Distributed Computing. 2023;36:29-43. doi:10.1007/s00446-022-00439-5
apa: Baig, M. A., Hendler, D., Milani, A., & Travers, C. (2023). Long-lived
counters with polylogarithmic amortized step complexity. Distributed Computing.
Springer Nature. https://doi.org/10.1007/s00446-022-00439-5
chicago: Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers.
“Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” Distributed
Computing. Springer Nature, 2023. https://doi.org/10.1007/s00446-022-00439-5.
ieee: M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with
polylogarithmic amortized step complexity,” Distributed Computing, vol.
36. Springer Nature, pp. 29–43, 2023.
ista: Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic
amortized step complexity. Distributed Computing. 36, 29–43.
mla: Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized
Step Complexity.” Distributed Computing, vol. 36, Springer Nature, 2023,
pp. 29–43, doi:10.1007/s00446-022-00439-5.
short: M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023)
29–43.
date_created: 2023-01-12T12:10:08Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-08-16T08:39:36Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/s00446-022-00439-5
external_id:
isi:
- '000890138700001'
intvolume: ' 36'
isi: 1
keyword:
- Computational Theory and Mathematics
- Computer Networks and Communications
- Hardware and Architecture
- Theoretical Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://drops.dagstuhl.de/opus/volltexte/2019/11310/
month: '03'
oa: 1
oa_version: Preprint
page: 29-43
publication: Distributed Computing
publication_identifier:
eissn:
- 1432-0452
issn:
- 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Long-lived counters with polylogarithmic amortized step complexity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2023'
...
---
_id: '12287'
abstract:
- lang: eng
text: We present criteria for establishing a triangulation of a manifold. Given
a manifold M, a simplicial complex A, and a map H from the underlying space of
A to M, our criteria are presented in local coordinate charts for M, and ensure
that H is a homeomorphism. These criteria do not require a differentiable structure,
or even an explicit metric on M. No Delaunay property of A is assumed. The result
provides a triangulation guarantee for algorithms that construct a simplicial
complex by working in local coordinate patches. Because the criteria are easily
verified in such a setting, they are expected to be of general use.
acknowledgement: "This work has been funded by the European Research Council under
the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations
of Geometric Understanding in Higher Dimensions). Arijit Ghosh is supported by Ramanujan
Fellowship (No. SB/S2/RJN-064/2015). Part of this work was done when Arijit Ghosh
was a Researcher at Max-Planck-Institute for Informatics, Germany, supported by
the IndoGerman Max Planck Center for Computer Science (IMPECS). Mathijs Wintraecken
also received funding from the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie grant agreement No. 754411 and the Austrian
Science Fund (FWF): M-3073. A part of the results described in this paper were presented
at SoCG 2018 and in [3]. \r\nOpen access funding provided by the Austrian Science
Fund (FWF)."
article_processing_charge: No
article_type: original
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Ramsay
full_name: Dyer, Ramsay
last_name: Dyer
- first_name: Arijit
full_name: Ghosh, Arijit
last_name: Ghosh
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. Local criteria for triangulating
general manifolds. Discrete & Computational Geometry. 2023;69:156-191.
doi:10.1007/s00454-022-00431-7
apa: Boissonnat, J.-D., Dyer, R., Ghosh, A., & Wintraecken, M. (2023). Local
criteria for triangulating general manifolds. Discrete & Computational
Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00431-7
chicago: Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken.
“Local Criteria for Triangulating General Manifolds.” Discrete & Computational
Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-022-00431-7.
ieee: J.-D. Boissonnat, R. Dyer, A. Ghosh, and M. Wintraecken, “Local criteria for
triangulating general manifolds,” Discrete & Computational Geometry,
vol. 69. Springer Nature, pp. 156–191, 2023.
ista: Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. 2023. Local criteria for triangulating
general manifolds. Discrete & Computational Geometry. 69, 156–191.
mla: Boissonnat, Jean-Daniel, et al. “Local Criteria for Triangulating General Manifolds.”
Discrete & Computational Geometry, vol. 69, Springer Nature, 2023,
pp. 156–91, doi:10.1007/s00454-022-00431-7.
short: J.-D. Boissonnat, R. Dyer, A. Ghosh, M. Wintraecken, Discrete & Computational
Geometry 69 (2023) 156–191.
date_created: 2023-01-16T10:04:06Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2023-08-01T12:47:32Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s00454-022-00431-7
ec_funded: 1
external_id:
isi:
- '000862193600001'
file:
- access_level: open_access
checksum: 46352e0ee71e460848f88685ca852681
content_type: application/pdf
creator: dernst
date_created: 2023-02-02T11:01:10Z
date_updated: 2023-02-02T11:01:10Z
file_id: '12488'
file_name: 2023_DiscreteCompGeometry_Boissonnat.pdf
file_size: 582850
relation: main_file
success: 1
file_date_updated: 2023-02-02T11:01:10Z
has_accepted_license: '1'
intvolume: ' 69'
isi: 1
keyword:
- Computational Theory and Mathematics
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Theoretical Computer Science
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 156-191
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
grant_number: M03073
name: Learning and triangulating manifolds via collapses
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Local criteria for triangulating general manifolds
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 69
year: '2023'
...
---
_id: '10842'
abstract:
- lang: eng
text: We determine the unique factorization of some polynomials over a finite local
commutative ring with identity explicitly. This solves and generalizes the main
conjecture of Qian, Shi and Solé in [13]. We also give some applications to enumeration
of certain generalized double circulant self-dual and linear complementary dual
(LCD) codes over some finite rings together with an application in asymptotic
coding theory.
acknowledgement: The authors would like to thank Prof. Dr. Minjia Shi for bringing
[13, Conjecture 3.5] to our attention. We would also like to thank the associate
editor and anonymous reviewers for their valuable comments and suggestions which
improved and clarified the manuscript.
article_processing_charge: No
article_type: original
author:
- first_name: Seyda
full_name: Köse, Seyda
id: 8ba3170d-dc85-11ea-9058-c4251c96a6eb
last_name: Köse
- first_name: Ferruh
full_name: Özbudak, Ferruh
last_name: Özbudak
citation:
ama: Köse S, Özbudak F. Factorization of some polynomials over finite local commutative
rings and applications to certain self-dual and LCD codes. Cryptography and
Communications. 2022;14(4):933-948. doi:10.1007/s12095-022-00557-8
apa: Köse, S., & Özbudak, F. (2022). Factorization of some polynomials over
finite local commutative rings and applications to certain self-dual and LCD codes.
Cryptography and Communications. Springer Nature. https://doi.org/10.1007/s12095-022-00557-8
chicago: Köse, Seyda, and Ferruh Özbudak. “Factorization of Some Polynomials over
Finite Local Commutative Rings and Applications to Certain Self-Dual and LCD Codes.”
Cryptography and Communications. Springer Nature, 2022. https://doi.org/10.1007/s12095-022-00557-8.
ieee: S. Köse and F. Özbudak, “Factorization of some polynomials over finite local
commutative rings and applications to certain self-dual and LCD codes,” Cryptography
and Communications, vol. 14, no. 4. Springer Nature, pp. 933–948, 2022.
ista: Köse S, Özbudak F. 2022. Factorization of some polynomials over finite local
commutative rings and applications to certain self-dual and LCD codes. Cryptography
and Communications. 14(4), 933–948.
mla: Köse, Seyda, and Ferruh Özbudak. “Factorization of Some Polynomials over Finite
Local Commutative Rings and Applications to Certain Self-Dual and LCD Codes.”
Cryptography and Communications, vol. 14, no. 4, Springer Nature, 2022,
pp. 933–48, doi:10.1007/s12095-022-00557-8.
short: S. Köse, F. Özbudak, Cryptography and Communications 14 (2022) 933–948.
date_created: 2022-03-10T12:16:19Z
date_published: 2022-07-01T00:00:00Z
date_updated: 2023-09-05T15:35:55Z
day: '01'
department:
- _id: GradSch
doi: 10.1007/s12095-022-00557-8
external_id:
isi:
- '000766422000002'
intvolume: ' 14'
isi: 1
issue: '4'
keyword:
- Applied Mathematics
- Computational Theory and Mathematics
- Computer Networks and Communications
language:
- iso: eng
month: '07'
oa_version: None
page: 933-948
publication: Cryptography and Communications
publication_identifier:
eissn:
- 1936-2455
issn:
- 1936-2447
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Factorization of some polynomials over finite local commutative rings and applications
to certain self-dual and LCD codes
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 14
year: '2022'
...
---
_id: '11447'
abstract:
- lang: eng
text: Empirical essays of fitness landscapes suggest that they may be rugged, that
is having multiple fitness peaks. Such fitness landscapes, those that have multiple
peaks, necessarily have special local structures, called reciprocal sign epistasis
(Poelwijk et al. in J Theor Biol 272:141–144, 2011). Here, we investigate the
quantitative relationship between the number of fitness peaks and the number of
reciprocal sign epistatic interactions. Previously, it has been shown (Poelwijk
et al. in J Theor Biol 272:141–144, 2011) that pairwise reciprocal sign epistasis
is a necessary but not sufficient condition for the existence of multiple peaks.
Applying discrete Morse theory, which to our knowledge has never been used in
this context, we extend this result by giving the minimal number of reciprocal
sign epistatic interactions required to create a given number of peaks.
acknowledgement: We are grateful to Herbert Edelsbrunner and Jeferson Zapata for helpful
discussions. Open access funding provided by Austrian Science Fund (FWF). Partially
supported by the ERC Consolidator (771209–CharFL) and the FWF Austrian Science Fund
(I5127-B) grants to FAK.
article_number: '74'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Raimundo J
full_name: Saona Urmeneta, Raimundo J
id: BD1DF4C4-D767-11E9-B658-BC13E6697425
last_name: Saona Urmeneta
orcid: 0000-0001-5103-038X
- first_name: Fyodor
full_name: Kondrashov, Fyodor
id: 44FDEF62-F248-11E8-B48F-1D18A9856A87
last_name: Kondrashov
orcid: 0000-0001-8243-4694
- first_name: Kseniia
full_name: Khudiakova, Kseniia
id: 4E6DC800-AE37-11E9-AC72-31CAE5697425
last_name: Khudiakova
orcid: 0000-0002-6246-1465
citation:
ama: Saona Urmeneta RJ, Kondrashov F, Khudiakova K. Relation between the number
of peaks and the number of reciprocal sign epistatic interactions. Bulletin
of Mathematical Biology. 2022;84(8). doi:10.1007/s11538-022-01029-z
apa: Saona Urmeneta, R. J., Kondrashov, F., & Khudiakova, K. (2022). Relation
between the number of peaks and the number of reciprocal sign epistatic interactions.
Bulletin of Mathematical Biology. Springer Nature. https://doi.org/10.1007/s11538-022-01029-z
chicago: Saona Urmeneta, Raimundo J, Fyodor Kondrashov, and Kseniia Khudiakova.
“Relation between the Number of Peaks and the Number of Reciprocal Sign Epistatic
Interactions.” Bulletin of Mathematical Biology. Springer Nature, 2022.
https://doi.org/10.1007/s11538-022-01029-z.
ieee: R. J. Saona Urmeneta, F. Kondrashov, and K. Khudiakova, “Relation between
the number of peaks and the number of reciprocal sign epistatic interactions,”
Bulletin of Mathematical Biology, vol. 84, no. 8. Springer Nature, 2022.
ista: Saona Urmeneta RJ, Kondrashov F, Khudiakova K. 2022. Relation between the
number of peaks and the number of reciprocal sign epistatic interactions. Bulletin
of Mathematical Biology. 84(8), 74.
mla: Saona Urmeneta, Raimundo J., et al. “Relation between the Number of Peaks and
the Number of Reciprocal Sign Epistatic Interactions.” Bulletin of Mathematical
Biology, vol. 84, no. 8, 74, Springer Nature, 2022, doi:10.1007/s11538-022-01029-z.
short: R.J. Saona Urmeneta, F. Kondrashov, K. Khudiakova, Bulletin of Mathematical
Biology 84 (2022).
date_created: 2022-06-17T16:16:15Z
date_published: 2022-06-17T00:00:00Z
date_updated: 2023-08-03T07:20:53Z
day: '17'
ddc:
- '510'
- '570'
department:
- _id: GradSch
- _id: NiBa
- _id: JaMa
doi: 10.1007/s11538-022-01029-z
ec_funded: 1
external_id:
isi:
- '000812509800001'
file:
- access_level: open_access
checksum: 05a1fe7d10914a00c2bca9b447993a65
content_type: application/pdf
creator: dernst
date_created: 2022-06-20T07:51:32Z
date_updated: 2022-06-20T07:51:32Z
file_id: '11455'
file_name: 2022_BulletinMathBiology_Saona.pdf
file_size: 463025
relation: main_file
success: 1
file_date_updated: 2022-06-20T07:51:32Z
has_accepted_license: '1'
intvolume: ' 84'
isi: 1
issue: '8'
keyword:
- Computational Theory and Mathematics
- General Agricultural and Biological Sciences
- Pharmacology
- General Environmental Science
- General Biochemistry
- Genetics and Molecular Biology
- General Mathematics
- Immunology
- General Neuroscience
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 26580278-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '771209'
name: Characterizing the fitness landscape on population and global scales
- _id: c098eddd-5a5b-11eb-8a69-abe27170a68f
grant_number: I05127
name: Evolutionary analysis of gene regulation
publication: Bulletin of Mathematical Biology
publication_identifier:
eissn:
- 1522-9602
issn:
- 0092-8240
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
link:
- relation: erratum
url: https://doi.org/10.1007/s11538-022-01118-z
scopus_import: '1'
status: public
title: Relation between the number of peaks and the number of reciprocal sign epistatic
interactions
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 84
year: '2022'
...
---
_id: '12129'
abstract:
- lang: eng
text: 'Given a finite point set P in general position in the plane, a full triangulation
of P is a maximal straight-line embedded plane graph on P. A partial triangulation
of P is a full triangulation of some subset P′ of P containing all extreme points
in P. A bistellar flip on a partial triangulation either flips an edge (called
edge flip), removes a non-extreme point of degree 3, or adds a point in P∖P′ as
vertex of degree 3. The bistellar flip graph has all partial triangulations as
vertices, and a pair of partial triangulations is adjacent if they can be obtained
from one another by a bistellar flip. The edge flip graph is defined with full
triangulations as vertices, and edge flips determining the adjacencies. Lawson
showed in the early seventies that these graphs are connected. The goal of this
paper is to investigate the structure of these graphs, with emphasis on their
vertex connectivity. For sets P of n points in the plane in general position,
we show that the edge flip graph is ⌈n/2−2⌉-vertex connected, and the bistellar
flip graph is (n−3)-vertex connected; both results are tight. The latter bound
matches the situation for the subfamily of regular triangulations (i.e., partial
triangulations obtained by lifting the points to 3-space and projecting back the
lower convex hull), where (n−3)-vertex connectivity has been known since the late
eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky
and Balinski’s Theorem. For the edge flip-graph, we additionally show that the
vertex connectivity is at least as large as (and hence equal to) the minimum degree
(i.e., the minimum number of flippable edges in any full triangulation), provided
that n is large enough. Our methods also yield several other results: (i) The
edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2−2⌉ (products
of associahedra) and the bistellar flip graph can be covered by graphs of polytopes
of dimension n−3 (products of secondary polytopes). (ii) A partial triangulation
is regular, if it has distance n−3 in the Hasse diagram of the partial order of
partial subdivisions from the trivial subdivision. (iii) All partial triangulations
of a point set are regular iff the partial order of partial subdivisions has height
n−3. (iv) There are arbitrarily large sets P with non-regular partial triangulations
and such that every proper subset has only regular triangulations, i.e., there
are no small certificates for the existence of non-regular triangulations.'
acknowledgement: "This is a full and revised version of [38] (on partial triangulations)
in Proceedings of the 36th Annual International Symposium on Computational Geometry
(SoCG‘20) and of some of the results in [37] (on full triangulations) in Proceedings
of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA‘20).\r\nThis
research started at the 11th Gremo’s Workshop on Open Problems (GWOP), Alp Sellamatt,
Switzerland, June 24–28, 2013, motivated by a question posed by Filip Mori´c on
full triangulations. Research was supported by the Swiss National Science Foundation
within the collaborative DACH project Arrangements and Drawings as SNSF Project
200021E-171681, and by IST Austria and Berlin Free University during a sabbatical
stay of the second author. We thank Michael Joswig, Jesús De Loera, and Francisco
Santos for helpful discussions on the topics of this paper, and Daniel Bertschinger
and Valentin Stoppiello for carefully reading earlier versions and for many helpful
comments.\r\nOpen access funding provided by the Swiss Federal Institute of Technology
Zürich"
article_processing_charge: No
article_type: original
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane.
Discrete & Computational Geometry. 2022;68(4):1227-1284. doi:10.1007/s00454-022-00436-2
apa: Wagner, U., & Welzl, E. (2022). Connectivity of triangulation flip graphs
in the plane. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00436-2
chicago: Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
in the Plane.” Discrete & Computational Geometry. Springer Nature,
2022. https://doi.org/10.1007/s00454-022-00436-2.
ieee: U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
plane,” Discrete & Computational Geometry, vol. 68, no. 4. Springer
Nature, pp. 1227–1284, 2022.
ista: Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the
plane. Discrete & Computational Geometry. 68(4), 1227–1284.
mla: Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the
Plane.” Discrete & Computational Geometry, vol. 68, no. 4, Springer
Nature, 2022, pp. 1227–84, doi:10.1007/s00454-022-00436-2.
short: U. Wagner, E. Welzl, Discrete & Computational Geometry 68 (2022) 1227–1284.
date_created: 2023-01-12T12:02:28Z
date_published: 2022-11-14T00:00:00Z
date_updated: 2023-08-04T08:51:08Z
day: '14'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1007/s00454-022-00436-2
external_id:
isi:
- '000883222200003'
file:
- access_level: open_access
checksum: 307e879d09e52eddf5b225d0aaa9213a
content_type: application/pdf
creator: dernst
date_created: 2023-01-23T11:10:03Z
date_updated: 2023-01-23T11:10:03Z
file_id: '12345'
file_name: 2022_DiscreteCompGeometry_Wagner.pdf
file_size: 1747581
relation: main_file
success: 1
file_date_updated: 2023-01-23T11:10:03Z
has_accepted_license: '1'
intvolume: ' 68'
isi: 1
issue: '4'
keyword:
- Computational Theory and Mathematics
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Theoretical Computer Science
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 1227-1284
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '7807'
relation: earlier_version
status: public
- id: '7990'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Connectivity of triangulation flip graphs in the plane
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 68
year: '2022'
...
---
_id: '12152'
abstract:
- lang: eng
text: ESCRT-III filaments are composite cytoskeletal polymers that can constrict
and cut cell membranes from the inside of the membrane neck. Membrane-bound ESCRT-III
filaments undergo a series of dramatic composition and geometry changes in the
presence of an ATP-consuming Vps4 enzyme, which causes stepwise changes in the
membrane morphology. We set out to understand the physical mechanisms involved
in translating the changes in ESCRT-III polymer composition into membrane deformation.
We have built a coarse-grained model in which ESCRT-III polymers of different
geometries and mechanical properties are allowed to copolymerise and bind to a
deformable membrane. By modelling ATP-driven stepwise depolymerisation of specific
polymers, we identify mechanical regimes in which changes in filament composition
trigger the associated membrane transition from a flat to a buckled state, and
then to a tubule state that eventually undergoes scission to release a small cargo-loaded
vesicle. We then characterise how the location and kinetics of polymer loss affects
the extent of membrane deformation and the efficiency of membrane neck scission.
Our results identify the near-minimal mechanical conditions for the operation
of shape-shifting composite polymers that sever membrane necks.
acknowledgement: "A.S . received an award from European Research Council (https://erc.europa.eu,
“NEPA\"\r\n802960), and an award from the Royal Society (https://royalsociety.org,
UF160266). L. H.-K.\r\nreceived an award from the Biotechnology and Biological Sciences
Research Council (https://\r\nwww.ukri.org/councils/bbsrc/). E. L. received an award
from the University College London (https://www.ucl.ac.uk/biophysics/news/2022/feb/applications-biop-brian-duff-and-ipls-summerundergraduate-studentships-now-open,
Brian Duff Undergraduate Summer Research Studentship). B.B. and A.S. received an
award from Volkswagen Foundation https://www.volkswagenstiftung.de/en/foundation,
Az 96727), and an award from Medical Research Council (https://www.ukri.org/councils/mrc,
MC_CF1226). A. R. received an\r\naward from the Swiss National Fund for Research
(https://www.snf.ch/en, 31003A_130520,\r\n31003A_149975, and 31003A_173087) and
an award from the European Research Council\r\nConsolidator (https://erc.europa.eu,
311536). The funders had no role in study design, data collection and analysis,
decision to publish, or preparation of the manuscript."
article_number: e1010586
article_processing_charge: No
article_type: original
author:
- first_name: Xiuyun
full_name: Jiang, Xiuyun
last_name: Jiang
- first_name: Lena
full_name: Harker-Kirschneck, Lena
last_name: Harker-Kirschneck
- first_name: Christian Eduardo
full_name: Vanhille-Campos, Christian Eduardo
id: 3adeca52-9313-11ed-b1ac-c170b2505714
last_name: Vanhille-Campos
- first_name: Anna-Katharina
full_name: Pfitzner, Anna-Katharina
last_name: Pfitzner
- first_name: Elene
full_name: Lominadze, Elene
last_name: Lominadze
- first_name: Aurélien
full_name: Roux, Aurélien
last_name: Roux
- first_name: Buzz
full_name: Baum, Buzz
last_name: Baum
- first_name: Anđela
full_name: Šarić, Anđela
id: bf63d406-f056-11eb-b41d-f263a6566d8b
last_name: Šarić
orcid: 0000-0002-7854-2139
citation:
ama: Jiang X, Harker-Kirschneck L, Vanhille-Campos CE, et al. Modelling membrane
reshaping by staged polymerization of ESCRT-III filaments. PLOS Computational
Biology. 2022;18(10). doi:10.1371/journal.pcbi.1010586
apa: Jiang, X., Harker-Kirschneck, L., Vanhille-Campos, C. E., Pfitzner, A.-K.,
Lominadze, E., Roux, A., … Šarić, A. (2022). Modelling membrane reshaping by staged
polymerization of ESCRT-III filaments. PLOS Computational Biology. Public
Library of Science. https://doi.org/10.1371/journal.pcbi.1010586
chicago: Jiang, Xiuyun, Lena Harker-Kirschneck, Christian Eduardo Vanhille-Campos,
Anna-Katharina Pfitzner, Elene Lominadze, Aurélien Roux, Buzz Baum, and Anđela
Šarić. “Modelling Membrane Reshaping by Staged Polymerization of ESCRT-III Filaments.”
PLOS Computational Biology. Public Library of Science, 2022. https://doi.org/10.1371/journal.pcbi.1010586.
ieee: X. Jiang et al., “Modelling membrane reshaping by staged polymerization
of ESCRT-III filaments,” PLOS Computational Biology, vol. 18, no. 10. Public
Library of Science, 2022.
ista: Jiang X, Harker-Kirschneck L, Vanhille-Campos CE, Pfitzner A-K, Lominadze
E, Roux A, Baum B, Šarić A. 2022. Modelling membrane reshaping by staged polymerization
of ESCRT-III filaments. PLOS Computational Biology. 18(10), e1010586.
mla: Jiang, Xiuyun, et al. “Modelling Membrane Reshaping by Staged Polymerization
of ESCRT-III Filaments.” PLOS Computational Biology, vol. 18, no. 10, e1010586,
Public Library of Science, 2022, doi:10.1371/journal.pcbi.1010586.
short: X. Jiang, L. Harker-Kirschneck, C.E. Vanhille-Campos, A.-K. Pfitzner, E.
Lominadze, A. Roux, B. Baum, A. Šarić, PLOS Computational Biology 18 (2022).
date_created: 2023-01-12T12:08:10Z
date_published: 2022-10-17T00:00:00Z
date_updated: 2023-08-04T09:03:21Z
day: '17'
ddc:
- '570'
department:
- _id: AnSa
doi: 10.1371/journal.pcbi.1010586
ec_funded: 1
external_id:
isi:
- '000924885500005'
file:
- access_level: open_access
checksum: bada6a7865e470cf42bbdfa67dd471d2
content_type: application/pdf
creator: dernst
date_created: 2023-01-24T10:45:01Z
date_updated: 2023-01-24T10:45:01Z
file_id: '12359'
file_name: 2022_PLoSCompBio_Jiang.pdf
file_size: 2641067
relation: main_file
success: 1
file_date_updated: 2023-01-24T10:45:01Z
has_accepted_license: '1'
intvolume: ' 18'
isi: 1
issue: '10'
keyword:
- Computational Theory and Mathematics
- Cellular and Molecular Neuroscience
- Genetics
- Molecular Biology
- Ecology
- Modeling and Simulation
- Ecology
- Evolution
- Behavior and Systematics
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: eba2549b-77a9-11ec-83b8-a81e493eae4e
call_identifier: H2020
grant_number: '802960'
name: 'Non-Equilibrium Protein Assembly: from Building Blocks to Biological Machines'
- _id: eba0f67c-77a9-11ec-83b8-cc8501b3e222
grant_number: '96752'
name: 'The evolution of trafficking: from archaea to eukaryotes'
publication: PLOS Computational Biology
publication_identifier:
issn:
- 1553-7358
publication_status: published
publisher: Public Library of Science
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://github.com/sharonJXY/3-filament-model
scopus_import: '1'
status: public
title: Modelling membrane reshaping by staged polymerization of ESCRT-III filaments
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 18
year: '2022'
...
---
_id: '12261'
abstract:
- lang: eng
text: 'Dose–response relationships are a general concept for quantitatively describing
biological systems across multiple scales, from the molecular to the whole-cell
level. A clinically relevant example is the bacterial growth response to antibiotics,
which is routinely characterized by dose–response curves. The shape of the dose–response
curve varies drastically between antibiotics and plays a key role in treatment,
drug interactions, and resistance evolution. However, the mechanisms shaping the
dose–response curve remain largely unclear. Here, we show in Escherichia coli
that the distinctively shallow dose–response curve of the antibiotic trimethoprim
is caused by a negative growth-mediated feedback loop: Trimethoprim slows growth,
which in turn weakens the effect of this antibiotic. At the molecular level, this
feedback is caused by the upregulation of the drug target dihydrofolate reductase
(FolA/DHFR). We show that this upregulation is not a specific response to trimethoprim
but follows a universal trend line that depends primarily on the growth rate,
irrespective of its cause. Rewiring the feedback loop alters the dose–response
curve in a predictable manner, which we corroborate using a mathematical model
of cellular resource allocation and growth. Our results indicate that growth-mediated
feedback loops may shape drug responses more generally and could be exploited
to design evolutionary traps that enable selection against drug resistance.'
acknowledged_ssus:
- _id: M-Shop
acknowledgement: This work was in part supported by Human Frontier Science Program
GrantRGP0042/2013, Marie Curie Career Integration Grant303507, AustrianScience Fund
(FWF) Grant P27201-B22, and German Research Foundation(DFG) Collaborative Research
Center (SFB)1310to TB. SAA was supportedby the European Union’s Horizon2020Research
and Innovation Programunder the Marie Skłodowska-Curie Grant agreement No707352.
We wouldlike to thank the Bollenbach group for regular fruitful discussions. We
areparticularly thankful for the technical assistance of Booshini Fernando andfor
discussions of the theoretical aspects with Gerrit Ansmann. We areindebted to Bor
Kavˇciˇc for invaluable advice, help with setting up theluciferase-based growth
monitoring system, and for sharing plasmids. Weacknowledge the IST Austria Miba
Machine Shop for their support inbuilding a housing for the stacker of the plate
reader, which enabled thehigh-throughput luciferase-based experiments. We are grateful
to RosalindAllen, Bor Kavˇciˇc and Dor Russ for feedback on the manuscript. Open
Accessfunding enabled and organized by Projekt DEAL.
article_number: e10490
article_processing_charge: No
article_type: original
author:
- first_name: Andreas
full_name: Angermayr, Andreas
id: 4677C796-F248-11E8-B48F-1D18A9856A87
last_name: Angermayr
orcid: 0000-0001-8619-2223
- first_name: Tin Yau
full_name: Pang, Tin Yau
last_name: Pang
- first_name: Guillaume
full_name: Chevereau, Guillaume
last_name: Chevereau
- first_name: Karin
full_name: Mitosch, Karin
id: 39B66846-F248-11E8-B48F-1D18A9856A87
last_name: Mitosch
- first_name: Martin J
full_name: Lercher, Martin J
last_name: Lercher
- first_name: Mark Tobias
full_name: Bollenbach, Mark Tobias
id: 3E6DB97A-F248-11E8-B48F-1D18A9856A87
last_name: Bollenbach
orcid: 0000-0003-4398-476X
citation:
ama: Angermayr A, Pang TY, Chevereau G, Mitosch K, Lercher MJ, Bollenbach MT. Growth‐mediated
negative feedback shapes quantitative antibiotic response. Molecular Systems
Biology. 2022;18(9). doi:10.15252/msb.202110490
apa: Angermayr, A., Pang, T. Y., Chevereau, G., Mitosch, K., Lercher, M. J., &
Bollenbach, M. T. (2022). Growth‐mediated negative feedback shapes quantitative
antibiotic response. Molecular Systems Biology. Embo Press. https://doi.org/10.15252/msb.202110490
chicago: Angermayr, Andreas, Tin Yau Pang, Guillaume Chevereau, Karin Mitosch, Martin
J Lercher, and Mark Tobias Bollenbach. “Growth‐mediated Negative Feedback Shapes
Quantitative Antibiotic Response.” Molecular Systems Biology. Embo Press,
2022. https://doi.org/10.15252/msb.202110490.
ieee: A. Angermayr, T. Y. Pang, G. Chevereau, K. Mitosch, M. J. Lercher, and M.
T. Bollenbach, “Growth‐mediated negative feedback shapes quantitative antibiotic
response,” Molecular Systems Biology, vol. 18, no. 9. Embo Press, 2022.
ista: Angermayr A, Pang TY, Chevereau G, Mitosch K, Lercher MJ, Bollenbach MT. 2022.
Growth‐mediated negative feedback shapes quantitative antibiotic response. Molecular
Systems Biology. 18(9), e10490.
mla: Angermayr, Andreas, et al. “Growth‐mediated Negative Feedback Shapes Quantitative
Antibiotic Response.” Molecular Systems Biology, vol. 18, no. 9, e10490,
Embo Press, 2022, doi:10.15252/msb.202110490.
short: A. Angermayr, T.Y. Pang, G. Chevereau, K. Mitosch, M.J. Lercher, M.T. Bollenbach,
Molecular Systems Biology 18 (2022).
date_created: 2023-01-16T09:58:34Z
date_published: 2022-09-01T00:00:00Z
date_updated: 2023-08-04T09:51:49Z
day: '01'
ddc:
- '570'
department:
- _id: ToBo
doi: 10.15252/msb.202110490
external_id:
isi:
- '000856482800001'
file:
- access_level: open_access
checksum: 8b1d8f5ea20c8408acf466435fb6ae01
content_type: application/pdf
creator: dernst
date_created: 2023-01-30T09:49:55Z
date_updated: 2023-01-30T09:49:55Z
file_id: '12446'
file_name: 2022_MolecularSystemsBio_Angermayr.pdf
file_size: 1098812
relation: main_file
success: 1
file_date_updated: 2023-01-30T09:49:55Z
has_accepted_license: '1'
intvolume: ' 18'
isi: 1
issue: '9'
keyword:
- Applied Mathematics
- Computational Theory and Mathematics
- General Agricultural and Biological Sciences
- General Immunology and Microbiology
- General Biochemistry
- Genetics and Molecular Biology
- Information Systems
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: Molecular Systems Biology
publication_identifier:
eissn:
- 1744-4292
publication_status: published
publisher: Embo Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Growth‐mediated negative feedback shapes quantitative antibiotic response
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 18
year: '2022'
...
---
_id: '12280'
abstract:
- lang: eng
text: 'In repeated interactions, players can use strategies that respond to the
outcome of previous rounds. Much of the existing literature on direct reciprocity
assumes that all competing individuals use the same strategy space. Here, we study
both learning and evolutionary dynamics of players that differ in the strategy
space they explore. We focus on the infinitely repeated donation game and compare
three natural strategy spaces: memory-1 strategies, which consider the last moves
of both players, reactive strategies, which respond to the last move of the co-player,
and unconditional strategies. These three strategy spaces differ in the memory
capacity that is needed. We compute the long term average payoff that is achieved
in a pairwise learning process. We find that smaller strategy spaces can dominate
larger ones. For weak selection, unconditional players dominate both reactive
and memory-1 players. For intermediate selection, reactive players dominate memory-1
players. Only for strong selection and low cost-to-benefit ratio, memory-1 players
dominate the others. We observe that the supergame between strategy spaces can
be a social dilemma: maximum payoff is achieved if both players explore a larger
strategy space, but smaller strategy spaces dominate.'
acknowledgement: "This work was supported by the European Research Council (https://erc.europa.eu/)\r\nCoG
863818 (ForM-SMArt) (to K.C.), and the European Research Council Starting Grant
850529: E-DIRECT (to C.H.). The funders had no role in study design, data collection
and analysis, decision to publish, or preparation of the manuscript."
article_number: e1010149
article_processing_charge: No
article_type: original
author:
- first_name: Laura
full_name: Schmid, Laura
id: 38B437DE-F248-11E8-B48F-1D18A9856A87
last_name: Schmid
orcid: 0000-0002-6978-7329
- first_name: Christian
full_name: Hilbe, Christian
id: 2FDF8F3C-F248-11E8-B48F-1D18A9856A87
last_name: Hilbe
orcid: 0000-0001-5116-955X
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Schmid L, Hilbe C, Chatterjee K, Nowak M. Direct reciprocity between individuals
that use different strategy spaces. PLOS Computational Biology. 2022;18(6).
doi:10.1371/journal.pcbi.1010149
apa: Schmid, L., Hilbe, C., Chatterjee, K., & Nowak, M. (2022). Direct reciprocity
between individuals that use different strategy spaces. PLOS Computational
Biology. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1010149
chicago: Schmid, Laura, Christian Hilbe, Krishnendu Chatterjee, and Martin Nowak.
“Direct Reciprocity between Individuals That Use Different Strategy Spaces.” PLOS
Computational Biology. Public Library of Science, 2022. https://doi.org/10.1371/journal.pcbi.1010149.
ieee: L. Schmid, C. Hilbe, K. Chatterjee, and M. Nowak, “Direct reciprocity between
individuals that use different strategy spaces,” PLOS Computational Biology,
vol. 18, no. 6. Public Library of Science, 2022.
ista: Schmid L, Hilbe C, Chatterjee K, Nowak M. 2022. Direct reciprocity between
individuals that use different strategy spaces. PLOS Computational Biology. 18(6),
e1010149.
mla: Schmid, Laura, et al. “Direct Reciprocity between Individuals That Use Different
Strategy Spaces.” PLOS Computational Biology, vol. 18, no. 6, e1010149,
Public Library of Science, 2022, doi:10.1371/journal.pcbi.1010149.
short: L. Schmid, C. Hilbe, K. Chatterjee, M. Nowak, PLOS Computational Biology
18 (2022).
date_created: 2023-01-16T10:02:51Z
date_published: 2022-06-14T00:00:00Z
date_updated: 2025-07-14T09:09:49Z
day: '14'
ddc:
- '000'
- '570'
department:
- _id: KrCh
doi: 10.1371/journal.pcbi.1010149
ec_funded: 1
external_id:
isi:
- '000843626800031'
pmid:
- '35700167'
file:
- access_level: open_access
checksum: 31b6b311b6731f1658277a9dfff6632c
content_type: application/pdf
creator: dernst
date_created: 2023-01-30T11:28:13Z
date_updated: 2023-01-30T11:28:13Z
file_id: '12460'
file_name: 2022_PlosCompBio_Schmid.pdf
file_size: 3143222
relation: main_file
success: 1
file_date_updated: 2023-01-30T11:28:13Z
has_accepted_license: '1'
intvolume: ' 18'
isi: 1
issue: '6'
keyword:
- Computational Theory and Mathematics
- Cellular and Molecular Neuroscience
- Genetics
- Molecular Biology
- Ecology
- Modeling and Simulation
- Ecology
- Evolution
- Behavior and Systematics
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
pmid: 1
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: PLOS Computational Biology
publication_identifier:
eissn:
- 1553-7358
publication_status: published
publisher: Public Library of Science
quality_controlled: '1'
scopus_import: '1'
status: public
title: Direct reciprocity between individuals that use different strategy spaces
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 18
year: '2022'
...
---
_id: '12286'
abstract:
- lang: eng
text: "Inspired by the study of loose cycles in hypergraphs, we define the loose
core in hypergraphs as a structurewhich mirrors the close relationship between
cycles and $2$-cores in graphs. We prove that in the $r$-uniform binomial random
hypergraph $H^r(n,p)$, the order of the loose core undergoes a phase transition
at a certain critical threshold and determine this order, as well as the number
of edges, asymptotically in the subcritical and supercritical regimes.
\r\nOur
main tool is an algorithm called CoreConstruct, which enables us to analyse a
peeling process for the loose core. By analysing this algorithm we determine the
asymptotic degree distribution of vertices in the loose core and in particular
how many vertices and edges the loose core contains. As a corollary we obtain
an improved upper bound on the length of the longest loose cycle in $H^r(n,p)$."
acknowledgement: 'Supported by Austrian Science Fund (FWF): I3747, W1230.'
article_number: P4.13
article_processing_charge: No
article_type: original
author:
- first_name: Oliver
full_name: Cooley, Oliver
id: 43f4ddd0-a46b-11ec-8df6-ef3703bd721d
last_name: Cooley
- first_name: Mihyun
full_name: Kang, Mihyun
last_name: Kang
- first_name: Julian
full_name: Zalla, Julian
last_name: Zalla
citation:
ama: Cooley O, Kang M, Zalla J. Loose cores and cycles in random hypergraphs. The
Electronic Journal of Combinatorics. 2022;29(4). doi:10.37236/10794
apa: Cooley, O., Kang, M., & Zalla, J. (2022). Loose cores and cycles in random
hypergraphs. The Electronic Journal of Combinatorics. The Electronic Journal
of Combinatorics. https://doi.org/10.37236/10794
chicago: Cooley, Oliver, Mihyun Kang, and Julian Zalla. “Loose Cores and Cycles
in Random Hypergraphs.” The Electronic Journal of Combinatorics. The Electronic
Journal of Combinatorics, 2022. https://doi.org/10.37236/10794.
ieee: O. Cooley, M. Kang, and J. Zalla, “Loose cores and cycles in random hypergraphs,”
The Electronic Journal of Combinatorics, vol. 29, no. 4. The Electronic
Journal of Combinatorics, 2022.
ista: Cooley O, Kang M, Zalla J. 2022. Loose cores and cycles in random hypergraphs.
The Electronic Journal of Combinatorics. 29(4), P4.13.
mla: Cooley, Oliver, et al. “Loose Cores and Cycles in Random Hypergraphs.” The
Electronic Journal of Combinatorics, vol. 29, no. 4, P4.13, The Electronic
Journal of Combinatorics, 2022, doi:10.37236/10794.
short: O. Cooley, M. Kang, J. Zalla, The Electronic Journal of Combinatorics 29
(2022).
date_created: 2023-01-16T10:03:57Z
date_published: 2022-10-21T00:00:00Z
date_updated: 2023-08-04T10:29:18Z
day: '21'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.37236/10794
external_id:
isi:
- '000876763300001'
file:
- access_level: open_access
checksum: 00122b2459f09b5ae43073bfba565e94
content_type: application/pdf
creator: dernst
date_created: 2023-01-30T11:45:13Z
date_updated: 2023-01-30T11:45:13Z
file_id: '12462'
file_name: 2022_ElecJournCombinatorics_Cooley_Kang_Zalla.pdf
file_size: 626953
relation: main_file
success: 1
file_date_updated: 2023-01-30T11:45:13Z
has_accepted_license: '1'
intvolume: ' 29'
isi: 1
issue: '4'
keyword:
- Computational Theory and Mathematics
- Geometry and Topology
- Theoretical Computer Science
- Applied Mathematics
- Discrete Mathematics and Combinatorics
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '10'
oa: 1
oa_version: Published Version
publication: The Electronic Journal of Combinatorics
publication_identifier:
eissn:
- 1077-8926
publication_status: published
publisher: The Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Loose cores and cycles in random hypergraphs
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 29
year: '2022'
...
---
_id: '11446'
abstract:
- lang: eng
text: Suppose that n is not a prime power and not twice a prime power. We prove
that for any Hausdorff compactum X with a free action of the symmetric group Sn,
there exists an Sn-equivariant map X→Rn whose image avoids the diagonal {(x,x,…,x)∈Rn∣x∈R}.
Previously, the special cases of this statement for certain X were usually proved
using the equivartiant obstruction theory. Such calculations are difficult and
may become infeasible past the first (primary) obstruction. We take a different
approach which allows us to prove the vanishing of all obstructions simultaneously.
The essential step in the proof is classifying the possible degrees of Sn-equivariant
maps from the boundary ∂Δn−1 of (n−1)-simplex to itself. Existence of equivariant
maps between spaces is important for many questions arising from discrete mathematics
and geometry, such as Kneser’s conjecture, the Square Peg conjecture, the Splitting
Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate
the utility of our result applying it to one such question, a specific instance
of envy-free division problem.
acknowledgement: S. Avvakumov has received funding from the European Research Council
under the European Union’s Seventh Framework Programme ERC Grant agreement ERC StG
716424–CASe. S. Kudrya was supported by the Austrian Academic Exchange Service (OeAD),
ICM-2019-13577.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
- first_name: Sergey
full_name: Kudrya, Sergey
id: ecf01965-d252-11ea-95a5-8ada5f6c6a67
last_name: Kudrya
citation:
ama: Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping
degree. Discrete & Computational Geometry. 2021;66(3):1202-1216. doi:10.1007/s00454-021-00299-z
apa: Avvakumov, S., & Kudrya, S. (2021). Vanishing of all equivariant obstructions
and the mapping degree. Discrete & Computational Geometry. Springer
Nature. https://doi.org/10.1007/s00454-021-00299-z
chicago: Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions
and the Mapping Degree.” Discrete & Computational Geometry. Springer
Nature, 2021. https://doi.org/10.1007/s00454-021-00299-z.
ieee: S. Avvakumov and S. Kudrya, “Vanishing of all equivariant obstructions and
the mapping degree,” Discrete & Computational Geometry, vol. 66, no.
3. Springer Nature, pp. 1202–1216, 2021.
ista: Avvakumov S, Kudrya S. 2021. Vanishing of all equivariant obstructions and
the mapping degree. Discrete & Computational Geometry. 66(3), 1202–1216.
mla: Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions
and the Mapping Degree.” Discrete & Computational Geometry, vol. 66,
no. 3, Springer Nature, 2021, pp. 1202–16, doi:10.1007/s00454-021-00299-z.
short: S. Avvakumov, S. Kudrya, Discrete & Computational Geometry 66 (2021)
1202–1216.
date_created: 2022-06-17T08:45:15Z
date_published: 2021-10-01T00:00:00Z
date_updated: 2023-02-23T13:26:41Z
day: '01'
doi: 10.1007/s00454-021-00299-z
extern: '1'
external_id:
arxiv:
- '1910.12628'
intvolume: ' 66'
issue: '3'
keyword:
- Computational Theory and Mathematics
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Theoretical Computer Science
language:
- iso: eng
month: '10'
oa_version: Preprint
page: 1202-1216
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '8182'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Vanishing of all equivariant obstructions and the mapping degree
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 66
year: '2021'
...
---
_id: '8940'
abstract:
- lang: eng
text: We quantise Whitney’s construction to prove the existence of a triangulation
for any C^2 manifold, so that we get an algorithm with explicit bounds. We also
give a new elementary proof, which is completely geometric.
acknowledgement: This work has been funded by the European Research Council under
the European Union’s ERC Grant Agreement Number 339025 GUDHI (Algorithmic Foundations
of Geometric Understanding in Higher Dimensions). The third author also received
funding from the European Union’s Horizon 2020 research and innovation programme
under the Marie Skłodowska-Curie Grant Agreement No. 754411. Open access funding
provided by the Institute of Science and Technology (IST Austria).
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Jean-Daniel
full_name: Boissonnat, Jean-Daniel
last_name: Boissonnat
- first_name: Siargey
full_name: Kachanovich, Siargey
last_name: Kachanovich
- first_name: Mathijs
full_name: Wintraecken, Mathijs
id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
last_name: Wintraecken
orcid: 0000-0002-7472-2220
citation:
ama: 'Boissonnat J-D, Kachanovich S, Wintraecken M. Triangulating submanifolds:
An elementary and quantified version of Whitney’s method. Discrete & Computational
Geometry. 2021;66(1):386-434. doi:10.1007/s00454-020-00250-8'
apa: 'Boissonnat, J.-D., Kachanovich, S., & Wintraecken, M. (2021). Triangulating
submanifolds: An elementary and quantified version of Whitney’s method. Discrete
& Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00250-8'
chicago: 'Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken.
“Triangulating Submanifolds: An Elementary and Quantified Version of Whitney’s
Method.” Discrete & Computational Geometry. Springer Nature, 2021.
https://doi.org/10.1007/s00454-020-00250-8.'
ieee: 'J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Triangulating submanifolds:
An elementary and quantified version of Whitney’s method,” Discrete & Computational
Geometry, vol. 66, no. 1. Springer Nature, pp. 386–434, 2021.'
ista: 'Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Triangulating submanifolds:
An elementary and quantified version of Whitney’s method. Discrete & Computational
Geometry. 66(1), 386–434.'
mla: 'Boissonnat, Jean-Daniel, et al. “Triangulating Submanifolds: An Elementary
and Quantified Version of Whitney’s Method.” Discrete & Computational Geometry,
vol. 66, no. 1, Springer Nature, 2021, pp. 386–434, doi:10.1007/s00454-020-00250-8.'
short: J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, Discrete & Computational
Geometry 66 (2021) 386–434.
date_created: 2020-12-12T11:07:02Z
date_published: 2021-07-01T00:00:00Z
date_updated: 2023-09-05T15:02:40Z
day: '01'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00250-8
ec_funded: 1
external_id:
isi:
- '000597770300001'
file:
- access_level: open_access
checksum: c848986091e56699dc12de85adb1e39c
content_type: application/pdf
creator: kschuh
date_created: 2021-08-06T09:52:29Z
date_updated: 2021-08-06T09:52:29Z
file_id: '9795'
file_name: 2021_DescreteCompGeopmetry_Boissonnat.pdf
file_size: 983307
relation: main_file
success: 1
file_date_updated: 2021-08-06T09:52:29Z
has_accepted_license: '1'
intvolume: ' 66'
isi: 1
issue: '1'
keyword:
- Theoretical Computer Science
- Computational Theory and Mathematics
- Geometry and Topology
- Discrete Mathematics and Combinatorics
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 386-434
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: 'Triangulating submanifolds: An elementary and quantified version of Whitney’s
method'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 66
year: '2021'
...
---
_id: '10211'
abstract:
- lang: eng
text: "We study the problem of recovering an unknown signal \U0001D465\U0001D465
given measurements obtained from a generalized linear model with a Gaussian sensing
matrix. Two popular solutions are based on a linear estimator \U0001D465\U0001D465^L
and a spectral estimator \U0001D465\U0001D465^s. The former is a data-dependent
linear combination of the columns of the measurement matrix, and its analysis
is quite simple. The latter is the principal eigenvector of a data-dependent matrix,
and a recent line of work has studied its performance. In this paper, we show
how to optimally combine \U0001D465\U0001D465^L and \U0001D465\U0001D465^s. At
the heart of our analysis is the exact characterization of the empirical joint
distribution of (\U0001D465\U0001D465,\U0001D465\U0001D465^L,\U0001D465\U0001D465^s)
in the high-dimensional limit. This allows us to compute the Bayes-optimal combination
of \U0001D465\U0001D465^L and \U0001D465\U0001D465^s, given the limiting distribution
of the signal \U0001D465\U0001D465. When the distribution of the signal is Gaussian,
then the Bayes-optimal combination has the form \U0001D703\U0001D465\U0001D465^L+\U0001D465\U0001D465^s
and we derive the optimal combination coefficient. In order to establish the limiting
distribution of (\U0001D465\U0001D465,\U0001D465\U0001D465^L,\U0001D465\U0001D465^s),
we design and analyze an approximate message passing algorithm whose iterates
give \U0001D465\U0001D465^L and approach \U0001D465\U0001D465^s. Numerical simulations
demonstrate the improvement of the proposed combination with respect to the two
methods considered separately."
acknowledgement: M. Mondelli would like to thank Andrea Montanari for helpful discussions.
All the authors would like to thank the anonymous reviewers for their helpful comments.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Christos
full_name: Thrampoulidis, Christos
last_name: Thrampoulidis
- first_name: Ramji
full_name: Venkataramanan, Ramji
last_name: Venkataramanan
citation:
ama: Mondelli M, Thrampoulidis C, Venkataramanan R. Optimal combination of linear
and spectral estimators for generalized linear models. Foundations of Computational
Mathematics. 2021. doi:10.1007/s10208-021-09531-x
apa: Mondelli, M., Thrampoulidis, C., & Venkataramanan, R. (2021). Optimal combination
of linear and spectral estimators for generalized linear models. Foundations
of Computational Mathematics. Springer. https://doi.org/10.1007/s10208-021-09531-x
chicago: Mondelli, Marco, Christos Thrampoulidis, and Ramji Venkataramanan. “Optimal
Combination of Linear and Spectral Estimators for Generalized Linear Models.”
Foundations of Computational Mathematics. Springer, 2021. https://doi.org/10.1007/s10208-021-09531-x.
ieee: M. Mondelli, C. Thrampoulidis, and R. Venkataramanan, “Optimal combination
of linear and spectral estimators for generalized linear models,” Foundations
of Computational Mathematics. Springer, 2021.
ista: Mondelli M, Thrampoulidis C, Venkataramanan R. 2021. Optimal combination of
linear and spectral estimators for generalized linear models. Foundations of Computational
Mathematics.
mla: Mondelli, Marco, et al. “Optimal Combination of Linear and Spectral Estimators
for Generalized Linear Models.” Foundations of Computational Mathematics,
Springer, 2021, doi:10.1007/s10208-021-09531-x.
short: M. Mondelli, C. Thrampoulidis, R. Venkataramanan, Foundations of Computational
Mathematics (2021).
date_created: 2021-11-03T10:59:08Z
date_published: 2021-08-17T00:00:00Z
date_updated: 2023-09-05T14:13:57Z
day: '17'
ddc:
- '510'
department:
- _id: MaMo
doi: 10.1007/s10208-021-09531-x
external_id:
arxiv:
- '2008.03326'
isi:
- '000685721000001'
file:
- access_level: open_access
checksum: 9ea12dd8045a0678000a3a59295221cb
content_type: application/pdf
creator: alisjak
date_created: 2021-12-13T15:47:54Z
date_updated: 2021-12-13T15:47:54Z
file_id: '10542'
file_name: 2021_Springer_Mondelli.pdf
file_size: 2305731
relation: main_file
success: 1
file_date_updated: 2021-12-13T15:47:54Z
has_accepted_license: '1'
isi: 1
keyword:
- Applied Mathematics
- Computational Theory and Mathematics
- Computational Mathematics
- Analysis
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Foundations of Computational Mathematics
publication_identifier:
eissn:
- 1615-3383
issn:
- 1615-3375
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimal combination of linear and spectral estimators for generalized linear
models
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2021'
...
---
_id: '8767'
abstract:
- lang: eng
text: Resources are rarely distributed uniformly within a population. Heterogeneity
in the concentration of a drug, the quality of breeding sites, or wealth can all
affect evolutionary dynamics. In this study, we represent a collection of properties
affecting the fitness at a given location using a color. A green node is rich
in resources while a red node is poorer. More colors can represent a broader spectrum
of resource qualities. For a population evolving according to the birth-death
Moran model, the first question we address is which structures, identified by
graph connectivity and graph coloring, are evolutionarily equivalent. We prove
that all properly two-colored, undirected, regular graphs are evolutionarily equivalent
(where “properly colored” means that no two neighbors have the same color). We
then compare the effects of background heterogeneity on properly two-colored graphs
to those with alternative schemes in which the colors are permuted. Finally, we
discuss dynamic coloring as a model for spatiotemporal resource fluctuations,
and we illustrate that random dynamic colorings often diminish the effects of
background heterogeneity relative to a proper two-coloring.
acknowledgement: 'We thank Igor Erovenko for many helpful comments on an earlier version
of this paper. : Army Research Laboratory (grant W911NF-18-2-0265) (M.A.N.); the
Bill & Melinda Gates Foundation (grant OPP1148627) (M.A.N.); the NVIDIA Corporation
(A.M.). The funders had no role in study design, data collection and analysis, decision
to publish, or preparation of the manuscript.'
article_number: e1008402
article_processing_charge: No
article_type: original
author:
- first_name: Kamran
full_name: Kaveh, Kamran
last_name: Kaveh
- first_name: Alex
full_name: McAvoy, Alex
last_name: McAvoy
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin A.
full_name: Nowak, Martin A.
last_name: Nowak
citation:
ama: Kaveh K, McAvoy A, Chatterjee K, Nowak MA. The Moran process on 2-chromatic
graphs. PLOS Computational Biology. 2020;16(11). doi:10.1371/journal.pcbi.1008402
apa: Kaveh, K., McAvoy, A., Chatterjee, K., & Nowak, M. A. (2020). The Moran
process on 2-chromatic graphs. PLOS Computational Biology. Public Library
of Science. https://doi.org/10.1371/journal.pcbi.1008402
chicago: Kaveh, Kamran, Alex McAvoy, Krishnendu Chatterjee, and Martin A. Nowak.
“The Moran Process on 2-Chromatic Graphs.” PLOS Computational Biology.
Public Library of Science, 2020. https://doi.org/10.1371/journal.pcbi.1008402.
ieee: K. Kaveh, A. McAvoy, K. Chatterjee, and M. A. Nowak, “The Moran process on
2-chromatic graphs,” PLOS Computational Biology, vol. 16, no. 11. Public
Library of Science, 2020.
ista: Kaveh K, McAvoy A, Chatterjee K, Nowak MA. 2020. The Moran process on 2-chromatic
graphs. PLOS Computational Biology. 16(11), e1008402.
mla: Kaveh, Kamran, et al. “The Moran Process on 2-Chromatic Graphs.” PLOS Computational
Biology, vol. 16, no. 11, e1008402, Public Library of Science, 2020, doi:10.1371/journal.pcbi.1008402.
short: K. Kaveh, A. McAvoy, K. Chatterjee, M.A. Nowak, PLOS Computational Biology
16 (2020).
date_created: 2020-11-18T07:20:23Z
date_published: 2020-11-05T00:00:00Z
date_updated: 2023-08-22T12:49:18Z
day: '05'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1371/journal.pcbi.1008402
external_id:
isi:
- '000591317200004'
file:
- access_level: open_access
checksum: 555456dd0e47bcf9e0994bcb95577e88
content_type: application/pdf
creator: dernst
date_created: 2020-11-18T07:26:10Z
date_updated: 2020-11-18T07:26:10Z
file_id: '8768'
file_name: 2020_PlosCompBio_Kaveh.pdf
file_size: 2498594
relation: main_file
success: 1
file_date_updated: 2020-11-18T07:26:10Z
has_accepted_license: '1'
intvolume: ' 16'
isi: 1
issue: '11'
keyword:
- Ecology
- Modelling and Simulation
- Computational Theory and Mathematics
- Genetics
- Ecology
- Evolution
- Behavior and Systematics
- Molecular Biology
- Cellular and Molecular Neuroscience
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
publication: PLOS Computational Biology
publication_identifier:
eissn:
- 1553-7358
issn:
- 1553-734X
publication_status: published
publisher: Public Library of Science
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Moran process on 2-chromatic graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 16
year: '2020'
...
---
_id: '14125'
abstract:
- lang: eng
text: "Motivation: Recent technological advances have led to an increase in the
production and availability of single-cell data. The ability to integrate a set
of multi-technology measurements would allow the identification of biologically
or clinically meaningful observations through the unification of the perspectives
afforded by each technology. In most cases, however, profiling technologies consume
the used cells and thus pairwise correspondences between datasets are lost. Due
to the sheer size single-cell datasets can acquire, scalable algorithms that are
able to universally match single-cell measurements carried out in one cell to
its corresponding sibling in another technology are needed.\r\nResults: We propose
Single-Cell data Integration via Matching (SCIM), a scalable approach to recover
such correspondences in two or more technologies. SCIM assumes that cells share
a common (low-dimensional) underlying structure and that the underlying cell distribution
is approximately constant across technologies. It constructs a technology-invariant
latent space using an autoencoder framework with an adversarial objective. Multi-modal
datasets are integrated by pairing cells across technologies using a bipartite
matching scheme that operates on the low-dimensional latent representations. We
evaluate SCIM on a simulated cellular branching process and show that the cell-to-cell
matches derived by SCIM reflect the same pseudotime on the simulated dataset.
Moreover, we apply our method to two real-world scenarios, a melanoma tumor sample
and a human bone marrow sample, where we pair cells from a scRNA dataset to their
sibling cells in a CyTOF dataset achieving 90% and 78% cell-matching accuracy
for each one of the samples, respectively."
article_processing_charge: No
article_type: original
author:
- first_name: Stefan G
full_name: Stark, Stefan G
last_name: Stark
- first_name: Joanna
full_name: Ficek, Joanna
last_name: Ficek
- first_name: Francesco
full_name: Locatello, Francesco
id: 26cfd52f-2483-11ee-8040-88983bcc06d4
last_name: Locatello
orcid: 0000-0002-4850-0683
- first_name: Ximena
full_name: Bonilla, Ximena
last_name: Bonilla
- first_name: Stéphane
full_name: Chevrier, Stéphane
last_name: Chevrier
- first_name: Franziska
full_name: Singer, Franziska
last_name: Singer
- first_name: Rudolf
full_name: Aebersold, Rudolf
last_name: Aebersold
- first_name: Faisal S
full_name: Al-Quaddoomi, Faisal S
last_name: Al-Quaddoomi
- first_name: Jonas
full_name: Albinus, Jonas
last_name: Albinus
- first_name: Ilaria
full_name: Alborelli, Ilaria
last_name: Alborelli
- first_name: Sonali
full_name: Andani, Sonali
last_name: Andani
- first_name: Per-Olof
full_name: Attinger, Per-Olof
last_name: Attinger
- first_name: Marina
full_name: Bacac, Marina
last_name: Bacac
- first_name: Daniel
full_name: Baumhoer, Daniel
last_name: Baumhoer
- first_name: Beatrice
full_name: Beck-Schimmer, Beatrice
last_name: Beck-Schimmer
- first_name: Niko
full_name: Beerenwinkel, Niko
last_name: Beerenwinkel
- first_name: Christian
full_name: Beisel, Christian
last_name: Beisel
- first_name: Lara
full_name: Bernasconi, Lara
last_name: Bernasconi
- first_name: Anne
full_name: Bertolini, Anne
last_name: Bertolini
- first_name: Bernd
full_name: Bodenmiller, Bernd
last_name: Bodenmiller
- first_name: Ximena
full_name: Bonilla, Ximena
last_name: Bonilla
- first_name: Ruben
full_name: Casanova, Ruben
last_name: Casanova
- first_name: Stéphane
full_name: Chevrier, Stéphane
last_name: Chevrier
- first_name: Natalia
full_name: Chicherova, Natalia
last_name: Chicherova
- first_name: Maya
full_name: D'Costa, Maya
last_name: D'Costa
- first_name: Esther
full_name: Danenberg, Esther
last_name: Danenberg
- first_name: Natalie
full_name: Davidson, Natalie
last_name: Davidson
- first_name: Monica-Andreea Dră
full_name: gan, Monica-Andreea Dră
last_name: gan
- first_name: Reinhard
full_name: Dummer, Reinhard
last_name: Dummer
- first_name: Stefanie
full_name: Engler, Stefanie
last_name: Engler
- first_name: Martin
full_name: Erkens, Martin
last_name: Erkens
- first_name: Katja
full_name: Eschbach, Katja
last_name: Eschbach
- first_name: Cinzia
full_name: Esposito, Cinzia
last_name: Esposito
- first_name: André
full_name: Fedier, André
last_name: Fedier
- first_name: Pedro
full_name: Ferreira, Pedro
last_name: Ferreira
- first_name: Joanna
full_name: Ficek, Joanna
last_name: Ficek
- first_name: Anja L
full_name: Frei, Anja L
last_name: Frei
- first_name: Bruno
full_name: Frey, Bruno
last_name: Frey
- first_name: Sandra
full_name: Goetze, Sandra
last_name: Goetze
- first_name: Linda
full_name: Grob, Linda
last_name: Grob
- first_name: Gabriele
full_name: Gut, Gabriele
last_name: Gut
- first_name: Detlef
full_name: Günther, Detlef
last_name: Günther
- first_name: Martina
full_name: Haberecker, Martina
last_name: Haberecker
- first_name: Pirmin
full_name: Haeuptle, Pirmin
last_name: Haeuptle
- first_name: Viola
full_name: Heinzelmann-Schwarz, Viola
last_name: Heinzelmann-Schwarz
- first_name: Sylvia
full_name: Herter, Sylvia
last_name: Herter
- first_name: Rene
full_name: Holtackers, Rene
last_name: Holtackers
- first_name: Tamara
full_name: Huesser, Tamara
last_name: Huesser
- first_name: Anja
full_name: Irmisch, Anja
last_name: Irmisch
- first_name: Francis
full_name: Jacob, Francis
last_name: Jacob
- first_name: Andrea
full_name: Jacobs, Andrea
last_name: Jacobs
- first_name: Tim M
full_name: Jaeger, Tim M
last_name: Jaeger
- first_name: Katharina
full_name: Jahn, Katharina
last_name: Jahn
- first_name: Alva R
full_name: James, Alva R
last_name: James
- first_name: Philip M
full_name: Jermann, Philip M
last_name: Jermann
- first_name: André
full_name: Kahles, André
last_name: Kahles
- first_name: Abdullah
full_name: Kahraman, Abdullah
last_name: Kahraman
- first_name: Viktor H
full_name: Koelzer, Viktor H
last_name: Koelzer
- first_name: Werner
full_name: Kuebler, Werner
last_name: Kuebler
- first_name: Jack
full_name: Kuipers, Jack
last_name: Kuipers
- first_name: Christian P
full_name: Kunze, Christian P
last_name: Kunze
- first_name: Christian
full_name: Kurzeder, Christian
last_name: Kurzeder
- first_name: Kjong-Van
full_name: Lehmann, Kjong-Van
last_name: Lehmann
- first_name: Mitchell
full_name: Levesque, Mitchell
last_name: Levesque
- first_name: Sebastian
full_name: Lugert, Sebastian
last_name: Lugert
- first_name: Gerd
full_name: Maass, Gerd
last_name: Maass
- first_name: Markus
full_name: Manz, Markus
last_name: Manz
- first_name: Philipp
full_name: Markolin, Philipp
last_name: Markolin
- first_name: Julien
full_name: Mena, Julien
last_name: Mena
- first_name: Ulrike
full_name: Menzel, Ulrike
last_name: Menzel
- first_name: Julian M
full_name: Metzler, Julian M
last_name: Metzler
- first_name: Nicola
full_name: Miglino, Nicola
last_name: Miglino
- first_name: Emanuela S
full_name: Milani, Emanuela S
last_name: Milani
- first_name: Holger
full_name: Moch, Holger
last_name: Moch
- first_name: Simone
full_name: Muenst, Simone
last_name: Muenst
- first_name: Riccardo
full_name: Murri, Riccardo
last_name: Murri
- first_name: Charlotte KY
full_name: Ng, Charlotte KY
last_name: Ng
- first_name: Stefan
full_name: Nicolet, Stefan
last_name: Nicolet
- first_name: Marta
full_name: Nowak, Marta
last_name: Nowak
- first_name: Patrick GA
full_name: Pedrioli, Patrick GA
last_name: Pedrioli
- first_name: Lucas
full_name: Pelkmans, Lucas
last_name: Pelkmans
- first_name: Salvatore
full_name: Piscuoglio, Salvatore
last_name: Piscuoglio
- first_name: Michael
full_name: Prummer, Michael
last_name: Prummer
- first_name: Mathilde
full_name: Ritter, Mathilde
last_name: Ritter
- first_name: Christian
full_name: Rommel, Christian
last_name: Rommel
- first_name: María L
full_name: Rosano-González, María L
last_name: Rosano-González
- first_name: Gunnar
full_name: Rätsch, Gunnar
last_name: Rätsch
- first_name: Natascha
full_name: Santacroce, Natascha
last_name: Santacroce
- first_name: Jacobo Sarabia del
full_name: Castillo, Jacobo Sarabia del
last_name: Castillo
- first_name: Ramona
full_name: Schlenker, Ramona
last_name: Schlenker
- first_name: Petra C
full_name: Schwalie, Petra C
last_name: Schwalie
- first_name: Severin
full_name: Schwan, Severin
last_name: Schwan
- first_name: Tobias
full_name: Schär, Tobias
last_name: Schär
- first_name: Gabriela
full_name: Senti, Gabriela
last_name: Senti
- first_name: Franziska
full_name: Singer, Franziska
last_name: Singer
- first_name: Sujana
full_name: Sivapatham, Sujana
last_name: Sivapatham
- first_name: Berend
full_name: Snijder, Berend
last_name: Snijder
- first_name: Bettina
full_name: Sobottka, Bettina
last_name: Sobottka
- first_name: Vipin T
full_name: Sreedharan, Vipin T
last_name: Sreedharan
- first_name: Stefan
full_name: Stark, Stefan
last_name: Stark
- first_name: Daniel J
full_name: Stekhoven, Daniel J
last_name: Stekhoven
- first_name: Alexandre PA
full_name: Theocharides, Alexandre PA
last_name: Theocharides
- first_name: Tinu M
full_name: Thomas, Tinu M
last_name: Thomas
- first_name: Markus
full_name: Tolnay, Markus
last_name: Tolnay
- first_name: Vinko
full_name: Tosevski, Vinko
last_name: Tosevski
- first_name: Nora C
full_name: Toussaint, Nora C
last_name: Toussaint
- first_name: Mustafa A
full_name: Tuncel, Mustafa A
last_name: Tuncel
- first_name: Marina
full_name: Tusup, Marina
last_name: Tusup
- first_name: Audrey Van
full_name: Drogen, Audrey Van
last_name: Drogen
- first_name: Marcus
full_name: Vetter, Marcus
last_name: Vetter
- first_name: Tatjana
full_name: Vlajnic, Tatjana
last_name: Vlajnic
- first_name: Sandra
full_name: Weber, Sandra
last_name: Weber
- first_name: Walter P
full_name: Weber, Walter P
last_name: Weber
- first_name: Rebekka
full_name: Wegmann, Rebekka
last_name: Wegmann
- first_name: Michael
full_name: Weller, Michael
last_name: Weller
- first_name: Fabian
full_name: Wendt, Fabian
last_name: Wendt
- first_name: Norbert
full_name: Wey, Norbert
last_name: Wey
- first_name: Andreas
full_name: Wicki, Andreas
last_name: Wicki
- first_name: Bernd
full_name: Wollscheid, Bernd
last_name: Wollscheid
- first_name: Shuqing
full_name: Yu, Shuqing
last_name: Yu
- first_name: Johanna
full_name: Ziegler, Johanna
last_name: Ziegler
- first_name: Marc
full_name: Zimmermann, Marc
last_name: Zimmermann
- first_name: Martin
full_name: Zoche, Martin
last_name: Zoche
- first_name: Gregor
full_name: Zuend, Gregor
last_name: Zuend
- first_name: Gunnar
full_name: Rätsch, Gunnar
last_name: Rätsch
- first_name: Kjong-Van
full_name: Lehmann, Kjong-Van
last_name: Lehmann
citation:
ama: 'Stark SG, Ficek J, Locatello F, et al. SCIM: Universal single-cell matching
with unpaired feature sets. Bioinformatics. 2020;36(Supplement_2):i919-i927.
doi:10.1093/bioinformatics/btaa843'
apa: 'Stark, S. G., Ficek, J., Locatello, F., Bonilla, X., Chevrier, S., Singer,
F., … Lehmann, K.-V. (2020). SCIM: Universal single-cell matching with unpaired
feature sets. Bioinformatics. Oxford University Press. https://doi.org/10.1093/bioinformatics/btaa843'
chicago: 'Stark, Stefan G, Joanna Ficek, Francesco Locatello, Ximena Bonilla, Stéphane
Chevrier, Franziska Singer, Rudolf Aebersold, et al. “SCIM: Universal Single-Cell
Matching with Unpaired Feature Sets.” Bioinformatics. Oxford University
Press, 2020. https://doi.org/10.1093/bioinformatics/btaa843.'
ieee: 'S. G. Stark et al., “SCIM: Universal single-cell matching with unpaired
feature sets,” Bioinformatics, vol. 36, no. Supplement_2. Oxford University
Press, pp. i919–i927, 2020.'
ista: 'Stark SG et al. 2020. SCIM: Universal single-cell matching with unpaired
feature sets. Bioinformatics. 36(Supplement_2), i919–i927.'
mla: 'Stark, Stefan G., et al. “SCIM: Universal Single-Cell Matching with Unpaired
Feature Sets.” Bioinformatics, vol. 36, no. Supplement_2, Oxford University
Press, 2020, pp. i919–27, doi:10.1093/bioinformatics/btaa843.'
short: S.G. Stark, J. Ficek, F. Locatello, X. Bonilla, S. Chevrier, F. Singer, R.
Aebersold, F.S. Al-Quaddoomi, J. Albinus, I. Alborelli, S. Andani, P.-O. Attinger,
M. Bacac, D. Baumhoer, B. Beck-Schimmer, N. Beerenwinkel, C. Beisel, L. Bernasconi,
A. Bertolini, B. Bodenmiller, X. Bonilla, R. Casanova, S. Chevrier, N. Chicherova,
M. D’Costa, E. Danenberg, N. Davidson, M.-A.D. gan, R. Dummer, S. Engler, M. Erkens,
K. Eschbach, C. Esposito, A. Fedier, P. Ferreira, J. Ficek, A.L. Frei, B. Frey,
S. Goetze, L. Grob, G. Gut, D. Günther, M. Haberecker, P. Haeuptle, V. Heinzelmann-Schwarz,
S. Herter, R. Holtackers, T. Huesser, A. Irmisch, F. Jacob, A. Jacobs, T.M. Jaeger,
K. Jahn, A.R. James, P.M. Jermann, A. Kahles, A. Kahraman, V.H. Koelzer, W. Kuebler,
J. Kuipers, C.P. Kunze, C. Kurzeder, K.-V. Lehmann, M. Levesque, S. Lugert, G.
Maass, M. Manz, P. Markolin, J. Mena, U. Menzel, J.M. Metzler, N. Miglino, E.S.
Milani, H. Moch, S. Muenst, R. Murri, C.K. Ng, S. Nicolet, M. Nowak, P.G. Pedrioli,
L. Pelkmans, S. Piscuoglio, M. Prummer, M. Ritter, C. Rommel, M.L. Rosano-González,
G. Rätsch, N. Santacroce, J.S. del Castillo, R. Schlenker, P.C. Schwalie, S. Schwan,
T. Schär, G. Senti, F. Singer, S. Sivapatham, B. Snijder, B. Sobottka, V.T. Sreedharan,
S. Stark, D.J. Stekhoven, A.P. Theocharides, T.M. Thomas, M. Tolnay, V. Tosevski,
N.C. Toussaint, M.A. Tuncel, M. Tusup, A.V. Drogen, M. Vetter, T. Vlajnic, S.
Weber, W.P. Weber, R. Wegmann, M. Weller, F. Wendt, N. Wey, A. Wicki, B. Wollscheid,
S. Yu, J. Ziegler, M. Zimmermann, M. Zoche, G. Zuend, G. Rätsch, K.-V. Lehmann,
Bioinformatics 36 (2020) i919–i927.
date_created: 2023-08-21T12:28:20Z
date_published: 2020-12-01T00:00:00Z
date_updated: 2023-09-11T10:21:00Z
day: '01'
department:
- _id: FrLo
doi: 10.1093/bioinformatics/btaa843
extern: '1'
external_id:
pmid:
- '33381818'
intvolume: ' 36'
issue: Supplement_2
keyword:
- Computational Mathematics
- Computational Theory and Mathematics
- Computer Science Applications
- Molecular Biology
- Biochemistry
- Statistics and Probability
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1093/bioinformatics/btaa843
month: '12'
oa: 1
oa_version: Published Version
page: i919-i927
pmid: 1
publication: Bioinformatics
publication_identifier:
eissn:
- 1367-4811
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://github.com/ratschlab/scim
scopus_import: '1'
status: public
title: 'SCIM: Universal single-cell matching with unpaired feature sets'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2020'
...
---
_id: '8459'
abstract:
- lang: eng
text: Nuclear magnetic resonance (NMR) is a powerful tool for observing the motion
of biomolecules at the atomic level. One technique, the analysis of relaxation
dispersion phenomenon, is highly suited for studying the kinetics and thermodynamics
of biological processes. Built on top of the relax computational environment for
NMR dynamics is a new dispersion analysis designed to be comprehensive, accurate
and easy-to-use. The software supports more models, both numeric and analytic,
than current solutions. An automated protocol, available for scripting and driving
the graphical user interface (GUI), is designed to simplify the analysis of dispersion
data for NMR spectroscopists. Decreases in optimization time are granted by parallelization
for running on computer clusters and by skipping an initial grid search by using
parameters from one solution as the starting point for another —using analytic
model results for the numeric models, taking advantage of model nesting, and using
averaged non-clustered results for the clustered analysis.
article_processing_charge: No
article_type: original
author:
- first_name: Sébastien
full_name: Morin, Sébastien
last_name: Morin
- first_name: Troels E
full_name: Linnet, Troels E
last_name: Linnet
- first_name: Mathilde
full_name: Lescanne, Mathilde
last_name: Lescanne
- first_name: Paul
full_name: Schanda, Paul
id: 7B541462-FAF6-11E9-A490-E8DFE5697425
last_name: Schanda
orcid: 0000-0002-9350-7606
- first_name: Gary S
full_name: Thompson, Gary S
last_name: Thompson
- first_name: Martin
full_name: Tollinger, Martin
last_name: Tollinger
- first_name: Kaare
full_name: Teilum, Kaare
last_name: Teilum
- first_name: Stéphane
full_name: Gagné, Stéphane
last_name: Gagné
- first_name: Dominique
full_name: Marion, Dominique
last_name: Marion
- first_name: Christian
full_name: Griesinger, Christian
last_name: Griesinger
- first_name: Martin
full_name: Blackledge, Martin
last_name: Blackledge
- first_name: Edward J
full_name: d’Auvergne, Edward J
last_name: d’Auvergne
citation:
ama: 'Morin S, Linnet TE, Lescanne M, et al. Relax: The analysis of biomolecular
kinetics and thermodynamics using NMR relaxation dispersion data. Bioinformatics.
2014;30(15):2219-2220. doi:10.1093/bioinformatics/btu166'
apa: 'Morin, S., Linnet, T. E., Lescanne, M., Schanda, P., Thompson, G. S., Tollinger,
M., … d’Auvergne, E. J. (2014). Relax: The analysis of biomolecular kinetics and
thermodynamics using NMR relaxation dispersion data. Bioinformatics. Oxford
University Press. https://doi.org/10.1093/bioinformatics/btu166'
chicago: 'Morin, Sébastien, Troels E Linnet, Mathilde Lescanne, Paul Schanda, Gary
S Thompson, Martin Tollinger, Kaare Teilum, et al. “Relax: The Analysis of Biomolecular
Kinetics and Thermodynamics Using NMR Relaxation Dispersion Data.” Bioinformatics.
Oxford University Press, 2014. https://doi.org/10.1093/bioinformatics/btu166.'
ieee: 'S. Morin et al., “Relax: The analysis of biomolecular kinetics and
thermodynamics using NMR relaxation dispersion data,” Bioinformatics, vol.
30, no. 15. Oxford University Press, pp. 2219–2220, 2014.'
ista: 'Morin S, Linnet TE, Lescanne M, Schanda P, Thompson GS, Tollinger M, Teilum
K, Gagné S, Marion D, Griesinger C, Blackledge M, d’Auvergne EJ. 2014. Relax:
The analysis of biomolecular kinetics and thermodynamics using NMR relaxation
dispersion data. Bioinformatics. 30(15), 2219–2220.'
mla: 'Morin, Sébastien, et al. “Relax: The Analysis of Biomolecular Kinetics and
Thermodynamics Using NMR Relaxation Dispersion Data.” Bioinformatics, vol.
30, no. 15, Oxford University Press, 2014, pp. 2219–20, doi:10.1093/bioinformatics/btu166.'
short: S. Morin, T.E. Linnet, M. Lescanne, P. Schanda, G.S. Thompson, M. Tollinger,
K. Teilum, S. Gagné, D. Marion, C. Griesinger, M. Blackledge, E.J. d’Auvergne,
Bioinformatics 30 (2014) 2219–2220.
date_created: 2020-09-18T10:08:07Z
date_published: 2014-08-01T00:00:00Z
date_updated: 2021-01-12T08:19:25Z
day: '01'
doi: 10.1093/bioinformatics/btu166
extern: '1'
intvolume: ' 30'
issue: '15'
keyword:
- Statistics and Probability
- Computational Theory and Mathematics
- Biochemistry
- Molecular Biology
- Computational Mathematics
- Computer Science Applications
language:
- iso: eng
month: '08'
oa_version: None
page: 2219-2220
publication: Bioinformatics
publication_identifier:
issn:
- 1367-4803
- 1460-2059
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
related_material:
link:
- relation: erratum
url: https://doi.org/10.1093/bioinformatics/btz397
status: public
title: 'Relax: The analysis of biomolecular kinetics and thermodynamics using NMR
relaxation dispersion data'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 30
year: '2014'
...
---
_id: '11683'
abstract:
- lang: eng
text: The vertex connectivity κ of a graph is the smallest number of vertices whose
deletion separates the graph or makes it trivial. We present the fastest known
deterministic algorithm for finding the vertex connectivity and a corresponding
separator. The time for a digraph having n vertices and m edges is O(min{κ3 +
n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized
algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have
nonnegative weights the weighted vertex connectivity is found in time O(κ1nmlog(n2/m))
where κ1 ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n2/m))
with error probability 1/2. The main algorithm combines two previous vertex connectivity
algorithms and a generalization of the preflow-push algorithm of Hao and Orlin
(1994, J. Algorithms17, 424–446) that computes edge connectivity.
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Satish
full_name: Rao, Satish
last_name: Rao
- first_name: Harold N.
full_name: Gabow, Harold N.
last_name: Gabow
citation:
ama: 'Henzinger MH, Rao S, Gabow HN. Computing vertex connectivity: New bounds from
old techniques. Journal of Algorithms. 2000;34(2):222-250. doi:10.1006/jagm.1999.1055'
apa: 'Henzinger, M. H., Rao, S., & Gabow, H. N. (2000). Computing vertex connectivity:
New bounds from old techniques. Journal of Algorithms. Elsevier. https://doi.org/10.1006/jagm.1999.1055'
chicago: 'Henzinger, Monika H, Satish Rao, and Harold N. Gabow. “Computing Vertex
Connectivity: New Bounds from Old Techniques.” Journal of Algorithms. Elsevier,
2000. https://doi.org/10.1006/jagm.1999.1055.'
ieee: 'M. H. Henzinger, S. Rao, and H. N. Gabow, “Computing vertex connectivity:
New bounds from old techniques,” Journal of Algorithms, vol. 34, no. 2.
Elsevier, pp. 222–250, 2000.'
ista: 'Henzinger MH, Rao S, Gabow HN. 2000. Computing vertex connectivity: New bounds
from old techniques. Journal of Algorithms. 34(2), 222–250.'
mla: 'Henzinger, Monika H., et al. “Computing Vertex Connectivity: New Bounds from
Old Techniques.” Journal of Algorithms, vol. 34, no. 2, Elsevier, 2000,
pp. 222–50, doi:10.1006/jagm.1999.1055.'
short: M.H. Henzinger, S. Rao, H.N. Gabow, Journal of Algorithms 34 (2000) 222–250.
date_created: 2022-07-28T08:56:10Z
date_published: 2000-02-01T00:00:00Z
date_updated: 2022-09-12T09:06:48Z
day: '01'
doi: 10.1006/jagm.1999.1055
extern: '1'
intvolume: ' 34'
issue: '2'
keyword:
- Computational Theory and Mathematics
- Computational Mathematics
- Control and Optimization
language:
- iso: eng
month: '02'
oa_version: None
page: 222-250
publication: Journal of Algorithms
publication_identifier:
issn:
- 0196-6774
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Computing vertex connectivity: New bounds from old techniques'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2000'
...