License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2020.1
URN: urn:nbn:de:0030-drops-127906
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12790/
Go to the corresponding LIPIcs Volume Portal

Zimerman, Galia R. ; Svetlitsky, Dina ; Zehavi, Meirav ; Ziv-Ukelson, Michal

Approximate Search for Known Gene Clusters in New Genomes Using PQ-Trees

pdf-format:
LIPIcs-WABI-2020-1.pdf (0.9 MB)

Abstract

We define a new problem in comparative genomics, denoted PQ-Tree Search, that takes as input a PQ-tree T representing the known gene orders of a gene cluster of interest, a gene-to-gene substitution scoring function h, integer parameters d_T and d_S, and a new genome S. The objective is to identify in S approximate new instances of the gene cluster that could vary from the known gene orders by genome rearrangements that are constrained by T, by gene substitutions that are governed by h, and by gene deletions and insertions that are bounded from above by d_T and d_S, respectively. We prove that the PQ-Tree Search problem is NP-hard and propose a parameterized algorithm that solves the optimization variant of PQ-Tree Search in O^*(2^{γ}) time, where γ is the maximum degree of a node in T and O^* is used to hide factors polynomial in the input size.
The algorithm is implemented as a search tool, denoted PQFinder, and applied to search for instances of chromosomal gene clusters in plasmids, within a dataset of 1,487 prokaryotic genomes. We report on 29 chromosomal gene clusters that are rearranged in plasmids, where the rearrangements are guided by the corresponding PQ-tree. One of these results, coding for a heavy metal efflux pump, is further analysed to exemplify how PQFinder can be harnessed to reveal interesting new structural variants of known gene clusters.

BibTeX - Entry

@InProceedings{zimerman_et_al:LIPIcs:2020:12790,
  author =	{Galia R. Zimerman and Dina Svetlitsky and Meirav Zehavi and Michal Ziv-Ukelson},
  title =	{{Approximate Search for Known Gene Clusters in New Genomes Using PQ-Trees}},
  booktitle =	{20th International Workshop on Algorithms in Bioinformatics (WABI 2020)},
  pages =	{1:1--1:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-161-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{172},
  editor =	{Carl Kingsford and Nadia Pisanti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12790},
  URN =		{urn:nbn:de:0030-drops-127906},
  doi =		{10.4230/LIPIcs.WABI.2020.1},
  annote =	{Keywords: PQ-Tree, Gene Cluster, Efflux Pump}
}

Keywords: PQ-Tree, Gene Cluster, Efflux Pump
Collection: 20th International Workshop on Algorithms in Bioinformatics (WABI 2020)
Issue Date: 2020
Date of publication: 25.08.2020
Supplementary Material: The code for the PQFinder tool as well as all the data needed to reconstruct the results are publicly available on GitHub (https://github.com/GaliaZim/PQFinder).

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI