3 Search Results for "Lind�n, Krister"

Document
DOI: 10.4230/LIPIcs.WABI.2019.13
Weighted Minimum-Length Rearrangement Scenarios

Authors: Pijus Simonaitis, Annie Chateau, and Krister M. Swenson

Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)

Abstract
We present the first known model of genome rearrangement with an arbitrary real-valued weight function on the rearrangements. It is based on the dominant model for the mathematical and algorithmic study of genome rearrangement, Double Cut and Join (DCJ). Our objective function is the sum or product of the weights of the DCJs in an evolutionary scenario, and the function can be minimized or maximized. If the likelihood of observing an independent DCJ was estimated based on biological conditions, for example, then this objective function could be the likelihood of observing the independent DCJs together in a scenario. We present an O(n⁴)-time dynamic programming algorithm solving the Minimum Cost Parsimonious Scenario (MCPS) problem for co-tailed genomes with n genes (or syntenic blocks). Combining this with our previous work on MCPS yields a polynomial-time algorithm for general genomes. The key theoretical contribution is a novel link between the parsimonious DCJ (or 2-break) scenarios and quadrangulations of a regular polygon. To demonstrate that our algorithm is fast enough to treat biological data, we run it on syntenic blocks constructed for Human paired with Chimpanzee, Gibbon, Mouse, and Chicken. We argue that the Human and Gibbon pair is a particularly interesting model for the study of weighted genome rearrangements.
Cite as

Pijus Simonaitis, Annie Chateau, and Krister M. Swenson. Weighted Minimum-Length Rearrangement Scenarios. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{simonaitis_et_al:LIPIcs.WABI.2019.13,
  author =	{Simonaitis, Pijus and Chateau, Annie and Swenson, Krister M.},
  title =	{{Weighted Minimum-Length Rearrangement Scenarios}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Huber, Katharina T. and Gusfield, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.13},
  URN =		{urn:nbn:de:0030-drops-110436},
  doi =		{10.4230/LIPIcs.WABI.2019.13},
  annote =	{Keywords: Weighted genome rearrangement, Double cut and join (DCJ), Edge switch, Minimum-weight quadrangulation}
}
Document
DOI: 10.4230/LIPIcs.WABI.2019.20
Rapidly Computing the Phylogenetic Transfer Index

Authors: Jakub Truszkowski, Olivier Gascuel, and Krister M. Swenson

Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)

Abstract
Given trees T and T_o on the same taxon set, the transfer index phi(b,T_o) is the number of taxa that need to be ignored so that the bipartition induced by branch b in T is equal to some bipartition in T_o. Recently, Lemoine et al. [Lemoine et al., 2018] used the transfer index to design a novel bootstrap analysis technique that improves on Felsenstein’s bootstrap on large, noisy data sets. In this work, we propose an algorithm that computes the transfer index for all branches b in T in O(n log^3 n) time, which improves upon the current O(n^2)-time algorithm by Lin, Rajan and Moret [Lin et al., 2012]. Our implementation is able to process pairs of trees with hundreds of thousands of taxa in minutes and considerably speeds up the method of Lemoine et al. on large data sets. We believe our algorithm can be useful for comparing large phylogenies, especially when some taxa are misplaced (e.g. due to horizontal gene transfer, recombination, or reconstruction errors).
Cite as

Jakub Truszkowski, Olivier Gascuel, and Krister M. Swenson. Rapidly Computing the Phylogenetic Transfer Index. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{truszkowski_et_al:LIPIcs.WABI.2019.20,
  author =	{Truszkowski, Jakub and Gascuel, Olivier and Swenson, Krister M.},
  title =	{{Rapidly Computing the Phylogenetic Transfer Index}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{20:1--20:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Huber, Katharina T. and Gusfield, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.20},
  URN =		{urn:nbn:de:0030-drops-110505},
  doi =		{10.4230/LIPIcs.WABI.2019.20},
  annote =	{Keywords: large phylogenies, bootstrap analysis, tree comparison, data structures on trees}
}
Document
DOI: 10.4230/DagMan.7.1.96
From Evaluating to Forecasting Performance: How to Turn Information Retrieval, Natural Language Processing and Recommender Systems into Predictive Sciences (Dagstuhl Perspectives Workshop 17442)

Authors: Nicola Ferro, Norbert Fuhr, Gregory Grefenstette, Joseph A. Konstan, Pablo Castells, Elizabeth M. Daly, Thierry Declerck, Michael D. Ekstrand, Werner Geyer, Julio Gonzalo, Tsvi Kuflik, Krister Lindén, Bernardo Magnini, Jian-Yun Nie, Raffaele Perego, Bracha Shapira, Ian Soboroff, Nava Tintarev, Karin Verspoor, Martijn C. Willemsen, and Justin Zobel

Published in: Dagstuhl Manifestos, Volume 7, Issue 1 (2018)

Abstract
We describe the state-of-the-art in performance modeling and prediction for Information Retrieval (IR), Natural Language Processing (NLP) and Recommender Systems (RecSys) along with its shortcomings and strengths. We present a framework for further research, identifying five major problem areas: understanding measures, performance analysis, making underlying assumptions explicit, identifying application features determining performance, and the development of prediction models describing the relationship between assumptions, features and resulting performance.
Cite as

Nicola Ferro, Norbert Fuhr, Gregory Grefenstette, Joseph A. Konstan, Pablo Castells, Elizabeth M. Daly, Thierry Declerck, Michael D. Ekstrand, Werner Geyer, Julio Gonzalo, Tsvi Kuflik, Krister Lindén, Bernardo Magnini, Jian-Yun Nie, Raffaele Perego, Bracha Shapira, Ian Soboroff, Nava Tintarev, Karin Verspoor, Martijn C. Willemsen, and Justin Zobel. From Evaluating to Forecasting Performance: How to Turn Information Retrieval, Natural Language Processing and Recommender Systems into Predictive Sciences (Dagstuhl Perspectives Workshop 17442). In Dagstuhl Manifestos, Volume 7, Issue 1, pp. 96-139, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{ferro_et_al:DagMan.7.1.96,
  author =	{Ferro, Nicola and Fuhr, Norbert and Grefenstette, Gregory and Konstan, Joseph A. and Castells, Pablo and Daly, Elizabeth M. and Declerck, Thierry and Ekstrand, Michael D. and Geyer, Werner and Gonzalo, Julio and Kuflik, Tsvi and Lind\'{e}n, Krister and Magnini, Bernardo and Nie, Jian-Yun and Perego, Raffaele and Shapira, Bracha and Soboroff, Ian and Tintarev, Nava and Verspoor, Karin and Willemsen, Martijn C. and Zobel, Justin},
  title =	{{From Evaluating to Forecasting Performance: How to Turn Information Retrieval, Natural Language Processing and Recommender Systems into Predictive Sciences (Dagstuhl Perspectives Workshop 17442)}},
  pages =	{96--139},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2018},
  volume =	{7},
  number =	{1},
  editor =	{Ferro, Nicola and Fuhr, Norbert and Grefenstette, Gregory and Konstan, Joseph A. and Castells, Pablo and Daly, Elizabeth M. and Declerck, Thierry and Ekstrand, Michael D. and Geyer, Werner and Gonzalo, Julio and Kuflik, Tsvi and Lind\'{e}n, Krister and Magnini, Bernardo and Nie, Jian-Yun and Perego, Raffaele and Shapira, Bracha and Soboroff, Ian and Tintarev, Nava and Verspoor, Karin and Willemsen, Martijn C. and Zobel, Justin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagMan.7.1.96},
  URN =		{urn:nbn:de:0030-drops-98987},
  doi =		{10.4230/DagMan.7.1.96},
  annote =	{Keywords: Information Systems, Formal models, Evaluation, Simulation, User Interaction}
}
  • Refine by Author
  • 2 Swenson, Krister M.
  • 1 Castells, Pablo
  • 1 Chateau, Annie
  • 1 Daly, Elizabeth M.
  • 1 Declerck, Thierry
  • Show More...

  • Refine by Classification
  • 2 Applied computing → Bioinformatics
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Double cut and join (DCJ)
  • 1 Edge switch
  • 1 Evaluation
  • 1 Formal models
  • 1 Information Systems
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2019
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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