5 Search Results for "Sivadasan, Naveen"


Document
Read Mapping on Genome Variation Graphs

Authors: Kavya Vaddadi, Rajgopal Srinivasan, and Naveen Sivadasan

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


Abstract
Genome variation graphs are natural candidates to represent a pangenome collection. In such graphs, common subsequences are encoded as vertices and the genomic variations are captured by introducing additional labeled vertices and directed edges. Unlike a linear reference, a reference graph allows a rich representation of the genomic diversities and avoids reference bias. We address the fundamental problem of mapping reads to genome variation graphs. We give a novel mapping algorithm V-MAP for efficient identification of small subgraph of the genome graph for optimal gapped alignment of the read. V-MAP creates space efficient index using locality sensitive minimizer signatures computed using a novel graph winnowing and graph embedding onto metric space for fast and accurate mapping. Experiments involving graph constructed from the 1000 Genomes data and using both real and simulated reads show that V-MAP is fast, memory efficient and can map short reads, as well as PacBio/Nanopore long reads with high accuracy. V-MAP performance was significantly better than the state-of-the-art, especially for long reads.

Cite as

Kavya Vaddadi, Rajgopal Srinivasan, and Naveen Sivadasan. Read Mapping on Genome Variation Graphs. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{vaddadi_et_al:LIPIcs.WABI.2019.7,
  author =	{Vaddadi, Kavya and Srinivasan, Rajgopal and Sivadasan, Naveen},
  title =	{{Read Mapping on Genome Variation Graphs}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{7:1--7: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.7},
  URN =		{urn:nbn:de:0030-drops-110375},
  doi =		{10.4230/LIPIcs.WABI.2019.7},
  annote =	{Keywords: read mapping, pangenome, genome variation graphs, locality sensitive hashing}
}
Document
Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion

Authors: R. B. Sandeep and Naveen Sivadasan

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)


Abstract
A diamond is a graph obtained by removing an edge from a complete graph on four vertices. A graph is diamond-free if it does not contain an induced diamond. The Diamond-free Edge Deletion problem asks to find whether there exist at most k edges in the input graph whose deletion results in a diamond-free graph. The problem was proved to be NP-complete and a polynomial kernel of O(k^4) vertices was found by Fellows et. al. (Discrete Optimization, 2011). In this paper, we give an improved kernel of O(k^3) vertices for Diamond-free Edge Deletion. We give an alternative proof of the NP-completeness of the problem and observe that it cannot be solved in time 2^{o(k)} * n^{O(1)}, unless the Exponential Time Hypothesis fails.

Cite as

R. B. Sandeep and Naveen Sivadasan. Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 365-376, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{sandeep_et_al:LIPIcs.IPEC.2015.365,
  author =	{Sandeep, R. B. and Sivadasan, Naveen},
  title =	{{Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{365--376},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.365},
  URN =		{urn:nbn:de:0030-drops-55976},
  doi =		{10.4230/LIPIcs.IPEC.2015.365},
  annote =	{Keywords: edge deletion problems, polynomial kernelization}
}
Document
Cubicity, Degeneracy, and Crossing Number

Authors: Abhijin Adiga, L. Sunil Chandran, and Rogers Mathew

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)


Abstract
A k-box B=(R_1,R_2,...,R_k), where each R_i is a closed interval on the real line, is defined to be the Cartesian product R_1 X R_2 X ... X R_k. If each R_i is a unit length interval, we call B a k-cube. Boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of k-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan. Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/0607092, 2006.] that, for a graph G with maximum degree \Delta, cub(G) <= \lceil 4(\Delta +1) ln n\rceil. In this paper we show that, for a k-degenerate graph G, cub(G) <= (k+2) \lceil 2e log n \rceil. Since k is at most \Delta and can be much lower, this clearly is a stronger result. We also give an efficient deterministic algorithm that runs in O(n^2k) time to output a 8k(\lceil 2.42 log n\rceil + 1) dimensional cube representation for G. The crossing number of a graph G, denoted as CR(G), is the minimum number of crossing pairs of edges, over all drawings of G in the plane. An important consequence of the above result is that if the crossing number of a graph G is t, then box(G) is O(t^{1/4}{\lceil log t\rceil}^{3/4}) . This bound is tight upto a factor of O((log t)^{3/4}). Let (P,\leq) be a partially ordered set and let G_{P} denote its underlying comparability graph. Let dim(P) denote the poset dimension of P. Another interesting consequence of our result is to show that dim(P) \leq 2(k+2) \lceil 2e \log n \rceil, where k denotes the degeneracy of G_{P}. Also, we get a deterministic algorithm that runs in O(n^2k) time to construct a 16k(\lceil 2.42 log n\rceil + 1) sized realizer for P. As far as we know, though very good upper bounds exist for poset dimension in terms of maximum degree of its underlying comparability graph, no upper bounds in terms of the degeneracy of the underlying comparability graph is seen in the literature.

Cite as

Abhijin Adiga, L. Sunil Chandran, and Rogers Mathew. Cubicity, Degeneracy, and Crossing Number. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 176-190, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{adiga_et_al:LIPIcs.FSTTCS.2011.176,
  author =	{Adiga, Abhijin and Chandran, L. Sunil and Mathew, Rogers},
  title =	{{Cubicity, Degeneracy, and Crossing Number}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{176--190},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.176},
  URN =		{urn:nbn:de:0030-drops-33428},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.176},
  annote =	{Keywords: Degeneracy, Cubicity, Boxicity, Crossing Number, Interval Graph, Intersection Graph, Poset Dimension, Comparability Graph}
}
Document
Online Scheduling with Bounded Migration

Authors: Peter Sanders, Naveen Sivadasan, and Martin Skutella

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)


Abstract
Consider the classical online scheduling problem where jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by~$\beta$ times the size of the arriving job. Our main result is a linear time `online approximation scheme', that is, a family of online algorithms with competitive ratio~$1+\epsilon$ and constant migration factor~$\beta(\epsilon)$, for any fixed~$\epsilon>0$. This result is of particular importance if considered in the context of sensitivity analysis: While a newly arriving job may force a complete change of the entire structure of an optimal schedule, only very limited `local' changes suffice to preserve near-optimal solutions. We believe that this concept will find wide application in its own right. We also present simple deterministic online algorithms with migration factors~$\beta=2$ and~$\beta=4/3$, respectively. Their competitive ratio~$3/2$ beats the lower bound on the performance of any online algorithm in the classical setting without migration. We also present improved algorithms and similar results for closely related problems. In particular, there is a short discussion of corresponding results for the objective to maximize the minimum load of a machine. The latter problem has an application for configuring storage servers that was the original motivation for this work.

Cite as

Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online Scheduling with Bounded Migration. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{sanders_et_al:DagSemProc.05031.22,
  author =	{Sanders, Peter and Sivadasan, Naveen and Skutella, Martin},
  title =	{{Online Scheduling with Bounded Migration}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.22},
  URN =		{urn:nbn:de:0030-drops-707},
  doi =		{10.4230/DagSemProc.05031.22},
  annote =	{Keywords: scheduling, sensitivity analysis, online algorithm}
}
Document
Topology Matters: Smoothed Competitiveness of Metrical Task Systems

Authors: Guido Schäfer and Naveen Sivadasan

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)


Abstract
We consider online problems that can be modeled as metrical task systems: An online algorithm resides in a graph of n nodes and may move in this graph at a cost equal to the distance. The algorithm has to service a sequence of tasks that arrive over time; each task specifies for each node a request cost that is incurred if the algorithm services the task in this particular node. The objective is to minimize the total request plus travel cost. Borodin, Linial and Saks gave a deterministic work function algorithm (WFA) for metrical task systems having a tight competitive ratio of 2n-1. We present a smoothed competitive analysis of WFA. Given an adversarial task sequence, we add some random noise to the request costs and analyze the competitive ratio of WFA on the perturbed sequence. We prove upper and matching lower bounds. Our analysis reveals that the smoothed competitive ratio of WFA is much better than its (worst case) competitive ratio and that it depends on several topological parameters of the graph underlying the metric, such as maximum degree, diameter, etc. For example, already for moderate perturbations, the smoothed competitive ratio of WFA is O(log(n)) on a clique and O(\sqrt{n}) on a line. We also provide the first average case analysis of WFA. For a large class of probability distributions, we prove that WFA has O(log(D)) expected competitive ratio, where D is the maximum degree of the underlying graph.

Cite as

Guido Schäfer and Naveen Sivadasan. Topology Matters: Smoothed Competitiveness of Metrical Task Systems. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{schafer_et_al:DagSemProc.05031.29,
  author =	{Sch\"{a}fer, Guido and Sivadasan, Naveen},
  title =	{{Topology Matters: Smoothed Competitiveness of Metrical Task Systems}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.29},
  URN =		{urn:nbn:de:0030-drops-684},
  doi =		{10.4230/DagSemProc.05031.29},
  annote =	{Keywords: online algorithm, metrical task systems, work function algorithm, smoothed competitive analysis}
}
  • Refine by Author
  • 4 Sivadasan, Naveen
  • 1 Adiga, Abhijin
  • 1 Chandran, L. Sunil
  • 1 Mathew, Rogers
  • 1 Sandeep, R. B.
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Computational genomics
  • 1 Computing methodologies → Combinatorial algorithms

  • Refine by Keyword
  • 2 online algorithm
  • 1 Boxicity
  • 1 Comparability Graph
  • 1 Crossing Number
  • 1 Cubicity
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2005
  • 1 2011
  • 1 2015
  • 1 2019

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