3 Search Results for "Willems, Erik P."

Document
DOI: 10.4230/LIPIcs.WABI.2025.10
DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs

Authors: Ali Ghaffaari, Alexander Schönhuth, and Tobias Marschall

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Determining the distance between two loci within a genomic region is a recurrent operation in various tasks in computational genomics. A notable example of this task arises in paired-end read mapping as a form of validation of distances between multiple alignments. While straightforward for a single genome, graph-based reference structures render the operation considerably more involved. Given the sheer number of such queries in a typical read mapping experiment, an efficient algorithm for answering distance queries is crucial. In this paper, we introduce DiVerG, a compact data structure as well as a fast and scalable algorithm, for constructing distance indexes for general sequence graphs on multi-core CPU and many-core GPU architectures. DiVerG is based on PairG [Jain et al., 2019], but overcomes the limitations of PairG by exploiting the extensive potential for improvements in terms of scalability and space efficiency. As a consequence, DiVerG can process substantially larger datasets, such as whole human genomes, which are unmanageable by PairG. DiVerG offers faster index construction time and consistently faster query time with gains proportional to the size of the underlying compact data structure. We demonstrate that our method performs favorably on multiple real datasets at various scales. DiVerG achieves superior performance over PairG; e.g. resulting to 2.5-4x speed-up in query time, 44-340x smaller index size, and 3-50x faster construction time for the genome graph of the MHC region, as a particularly variable region of the human genome. The implementation is available at: https://github.com/cartoonist/diverg
Cite as

Ali Ghaffaari, Alexander Schönhuth, and Tobias Marschall. DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ghaffaari_et_al:LIPIcs.WABI.2025.10,
  author =	{Ghaffaari, Ali and Sch\"{o}nhuth, Alexander and Marschall, Tobias},
  title =	{{DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{10:1--10:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.10},
  URN =		{urn:nbn:de:0030-drops-239369},
  doi =		{10.4230/LIPIcs.WABI.2025.10},
  annote =	{Keywords: Sequence graph, distance index, read mapping, sparse matrix}
}
Document
DOI: 10.4230/DagSemProc.10491.6
10491 Results of the break-out group: Movement Data of Vervet Monkeys

Authors: Erik P. Willems, Kevin Buchin, and Urska Demsar

Published in: Dagstuhl Seminar Proceedings, Volume 10491, Representation, Analysis and Visualization of Moving Objects (2011)

Abstract
Discussions in this group focused on a particular problem that arises in animal movement ecology: how to link data describing movement (i.e. sequential GPS- coordinates collected on wild and free-ranging animals) with geographical and environmental context (i.e. properties of the internal and external environment within which the animals move). Our case study comprised a spatio-temporal data set on the movement of a group of vervet monkeys (Cercopithecus aethiops) over a twelve months observation period. We focused on two topics: context-aware estimation of home range area and multivariate visualisation of context data.
Cite as

Erik P. Willems, Kevin Buchin, and Urska Demsar. 10491 Results of the break-out group: Movement Data of Vervet Monkeys. In Representation, Analysis and Visualization of Moving Objects. Dagstuhl Seminar Proceedings, Volume 10491, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{willems_et_al:DagSemProc.10491.6,
  author =	{Willems, Erik P. and Buchin, Kevin and Demsar, Urska},
  title =	{{10491 Results of the break-out group: Movement Data of Vervet Monkeys}},
  booktitle =	{Representation, Analysis and Visualization of Moving Objects},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10491},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Bettina Speckmann and Emiel Van Loon and Robert Weibel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10491.6},
  URN =		{urn:nbn:de:0030-drops-29908},
  doi =		{10.4230/DagSemProc.10491.6},
  annote =	{Keywords: Visualisation}
}
Document
DOI: 10.4230/DagSemProc.10491.8
10491 Results of the break-out group: Visualisation

Authors: Kevin Buchin, Urska Demsar, Aidan Slingsby, and Erik P. Willems

Published in: Dagstuhl Seminar Proceedings, Volume 10491, Representation, Analysis and Visualization of Moving Objects (2011)

Abstract
In this group we decided to collect literature that we were familiar with that best illustrated how movement data in the form of trajectories can be visualised. In this report we categorise methods based on what part of the data space is shown, i.e. geographical space, temporal space or attribute space, some combination thereof or an aggregation in one or more of the space components. Methods that use computational methods for pattern recognition in combination with visual methods form a separate category. However, these categories are only what we came up with during our short discussion and are therefore not fixed, nor are they mutually exclusive (i.e. there is certain overlap of methods) and should be extended/redefined as required in a more exhaustive literature review in the future.
Cite as

Kevin Buchin, Urska Demsar, Aidan Slingsby, and Erik P. Willems. 10491 Results of the break-out group: Visualisation. In Representation, Analysis and Visualization of Moving Objects. Dagstuhl Seminar Proceedings, Volume 10491, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:DagSemProc.10491.8,
  author =	{Buchin, Kevin and Demsar, Urska and Slingsby, Aidan and Willems, Erik P.},
  title =	{{10491 Results of the break-out group: Visualisation}},
  booktitle =	{Representation, Analysis and Visualization of Moving Objects},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10491},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Bettina Speckmann and Emiel Van Loon and Robert Weibel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10491.8},
  URN =		{urn:nbn:de:0030-drops-29864},
  doi =		{10.4230/DagSemProc.10491.8},
  annote =	{Keywords: Visualisation}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 2 2011

  • Refine by Author
  • 2 Buchin, Kevin
  • 2 Demsar, Urska
  • 2 Willems, Erik P.
  • 1 Ghaffaari, Ali
  • 1 Marschall, Tobias
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 2 DagSemProc

  • Refine by Classification
  • 1 Applied computing → Computational genomics
  • 1 Mathematics of computing → Paths and connectivity problems

  • Refine by Keyword
  • 2 Visualisation
  • 1 Sequence graph
  • 1 distance index
  • 1 read mapping
  • 1 sparse matrix

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact