references.bib

@inproceedings{alenex2020,
  title={Reverse-Safe Data Structures for Text Indexing},
  author={Bernardini, G. and Chen, H. and Fici, G. and Loukides, G. and Pissis, S. P.},
  booktitle={22nd ALENEX},
  pages={199--213},
  year={2020},
  }  
@inproceedings{icdm2020,
title={Hide and Mine in Strings: Hardness and Algorithms},
author={Bernardini, G and Conte, A and  Gourdel, G and Grossi, R and Loukides, G and Pisanti, N and Pissis, S. P. and Punzi, G and  Stougie, L and Sweering, M},
booktitle={20th ICDM},
year={2020}
}

@inproceedings{cpm2020,
author={G. Bernardini and H. Chen and  G. Loukides and N. Pisanti and S. P. Pissis and L. Stougie and M. Sweering},
title={String Sanitization under Edit Distance},
booktitle={31st CPM},
year={2020},
pages =	{7:1--7:14}
}

@inproceedings{gibney2020efficient,
  title={An Efficient Elastic-Degenerate Text Index? Not Likely},
  author={Gibney, Daniel},
  booktitle={International Symposium on String Processing and Information Retrieval},
  pages={76--88},
  year={2020},
  organization={Springer}
}

@inproceedings{pkdd2019,
author = {Bernardini, G. and Chen, H. and Conte, A. and Grossi, R. and Loukides, G. and Pisanti, N. and Pissis, S. P. and Rosone, G.},
 booktitle = {ECML/PKDD},
 year = {2019},
pages = {627--644},
title = {String Sanitization: A Combinatorial Approach}
}

@article{tkdd2020,
author = {Bernardini, G. and Chen, H. and Conte, A. and Grossi, R. and Loukides, G. and Pisanti, N. and Pissis, S. P. and Rosone, G. and Sweering, M.},
year = {2020},
journal = {TKDD},
title = {Combinatorial Algorithms for String Sanitization}
}

@InProceedings{ICALP2019,
  author =	{Giulia Bernardini and Pawel Gawrychowski and Nadia Pisanti and Solon P. Pissis and Giovanna Rosone},
  title =	{{Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication}},
  booktitle =	{46th ICALP},
  pages =	{21:1--21:15},
  _series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  year =	{2019},
  _volume =	{132}
}

@article{tcs2020,
  author    = {Giulia Bernardini and
               Nadia Pisanti and
               Solon P. Pissis and
               Giovanna Rosone},
  title     = {Approximate pattern matching on elastic-degenerate text},
  journal   = {Theor. Comput. Sci.},
  volume    = {812},
  pages     = {109--122},
  year      = {2020}
}

@inproceedings{wabi18,
  author    = {M. Alzamel and
			   L.A.K.~Ayad and
               G. Bernardini and
               R. Grossi and
               C.S.~Iliopoulos and
               N. Pisanti and
               S.P.~Pissis and
               G. Rosone},
  title =	{{Degenerate string comparison and applications}},
  booktitle =	{18th WABI},
  pages =	{21:1--21:14},
  _series =	{LIPIcs},
  year =	{2018},
  _volume =	{113}
}

@inproceedings{CPM2019,
  author =	{Giulia Bernardini and Paola Bonizzoni and Gianluca Della Vedova and Murray Patterson},
  title =	{A Rearrangement Distance for Fully-Labelled Trees},
  booktitle =	{30th CPM},
  pages =	{28:1--28:15},
  year = {2019}
}

@InProceedings{CPM2020trees,
  author =	{Giulia Bernardini and Paola Bonizzoni and Paweł Gawrychowski},
  title =	{{On Two Measures of Distance Between Fully-Labelled Trees}},
  booktitle =	{31st CPM},
  pages =	{6:1--6:16},
  year =	{2020}
}


@inproceedings{SEA2018,
  author    = {S.P. Pissis and
               A. Retha},
  title     = {Dictionary Matching in Elastic-Degenerate Texts with Applications in Searching {VCF} Files On-line},
  booktitle = {17th SEA},
  pages     = {16:1--16:14},
  year      = {2018},
   _series =	{LIPIcs},
  _volume =	{103}
 }
 
 @article{sopang,
author = {A. Cis\l{}ak and S. Grabowski and J. Holub},
title = {{SOPanG}: online text searching over a pan-genome},
journal = {Bioinformatics},
volume    = {34},
  number    = {24},
pages = {4290--4292},
year = {2018}
}

@INPROCEEDINGS{anliu,
author={A. {Liu} and K. {Zhengy} and L. {Liz} and G. {Liu} and L. {Zhao} and X. {Zhou}},
booktitle={31st ICDE},
title={Efficient secure similarity computation on encrypted trajectory data},
year={2015},
pages={66-77}, 
}

 @inproceedings{odesa,
  author    = {G. Loukides and
               R. Gwadera},
  title     = {Optimal event sequence sanitization},
  booktitle = {15th SDM},
  year      = {2015},
  pages     = {775--783}
  }
  
  @inproceedings{george,
   author    = {George Theodorakopoulos and
               Reza Shokri and
               Carmela Troncoso and
               Jean{-}Pierre Hubaux and
               Jean{-}Yves Le Boudec},
 title = {Prolonging the Hide-and-Seek Game: Optimal Trajectory Privacy for Location-Based Services},
 booktitle = {13th WPES},
 year = {2014},
 pages = {73--82},
 }
 
 @INPROCEEDINGS{netflix,
author={A. {Narayanan} and V. {Shmatikov}},
booktitle={S\&P},
title={Robust De-anonymization of Large Sparse Datasets},
year={2008},
pages={111--125}, 
}

@inproceedings{brad,
author={B. Malin and L. Sweeney},
year={2000},
title={Determining the identifiability of {DNA} database entries}, 
booktitle={AMIA},
pages={537-541},
}

@article{abul,
  author    = {O. Abul and
               F. Bonchi and
               F. Giannotti},
  title     = {Hiding Sequential and Spatiotemporal Patterns},
  journal   = {TKDE},
  volume    = {22},
  number    = {12},
  pages     = {1709--1723},
  year      = {2010},
  }
  
  @inproceedings{liyue,
 author = {L. Bonomi and L. Fan and H. Jin},
 title = {An Information-Theoretic Approach to Individual Sequential Data Sanitization},
 booktitle = {9th WSDM},
 year = {2016},
  pages = {337--346},
 }
 
 @inproceedings{sbsh,
 author = {A. Gkoulalas-Divanis and G. Loukides},
 title = {Revisiting Sequential Pattern Hiding to Enhance Utility},
 booktitle = {17th KDD},
 year = {2011},
 pages = {1316--1324},
 }
 
 @article{DBLP:journals/almob/GrossiIMPPRV16,
    author    = {Roberto Grossi and
               Costas S. Iliopoulos and
               Robert Mercas and
               Nadia Pisanti and
               Solon P. Pissis and
               Ahmad Retha and
               Fatima Vayani},
  title     = {Circular sequence comparison: algorithms and applications},
  journal   = {AMB},
  volume    = {11},
  pages     = {12},
  year      = {2016},
}

@article{DBLP:journals/bmcbi/Pissis14,
  author    = {Solon P. Pissis},
  title     = {{MoTeX-II}: structured {MoTif eXtraction} from large-scale datasets},
  journal   = {{BMC} Bioinformatics},
  volume    = {15},
  pages     = {235},
  year      = {2014}
}

@Article{vldbj08,
author="L. Jin and C. Li 
and R. Vernica",
title="SEPIA: estimating selectivities of approximate string predicates in large Databases",
journal="The VLDB Journal",
year="2008",
volume="17",
number="5",
pages="1213--1229",
}

 @INPROCEEDINGS{icde19,
author={Z. {Wen} and D. {Deng} and R. {Zhang} and R. {Kotagiri}},
booktitle={35th ICDE},
title={2ED: An Efficient Entity Extraction Algorithm Using Two-Level Edit-Distance},
year={2019},
pages={998-1009}, 
}

@ARTICLE{tkde14qa,
author={W. {Lu} and X. {Du} and M. {Hadjieleftheriou} and B. C. {Ooi}},
journal={TKDE},
title={Efficiently Supporting Edit Distance Based String Similarity Search Using B$^+$-Trees},
year={2014},
volume={26},
number={12},
pages={2983-2996}, 
}

@INPROCEEDINGS{icassp,
author={J. {Droppo} and A. {Acero}},
booktitle={35th ICASSP},
title={Context dependent phonetic string edit distance for automatic speech recognition},
year={2010},
pages={4358-4361}, 
}

@inproceedings{icdm13,
  author    = {R. Gwadera and
               A. Gkoulalas-Divanis and
               G. Loukides},
  title     = {Permutation-Based Sequential Pattern Hiding},
  booktitle = {13th ICDM},
  year      = {2013},
  pages     = {241-250},
}

 @inproceedings{streamevent,
 author = {D. Wang and Y. He and E. Rundensteiner and J. F. Naughton},
 title = {Utility-maximizing Event Stream Suppression},
 booktitle = {39th SIGMOD},
 year = {2013},
 pages = {589--600},
 }
 
 @Article{condensation,
author={C. C. Aggarwal and P. S. Yu},
title="A framework for condensation-based anonymization of string data",
journal="DMKD",
year="2008",
volume="16",
number="3",
pages="251--275",
}
 
  @inproceedings{bonomi,
 author = {L. Bonomi and L. Xiong},
 title = {A Two-phase Algorithm for Mining Sequential Patterns with Differential Privacy},
 booktitle = {22nd CIKM},
 year = {2013},
  pages = {269--278},
 }
 
 @article{brendel,
author = { Volker   Brendel  and  Jacques S.   Beckmann  and  Edward N.   Trifonov },
title = {Linguistics of Nucleotide Sequences: Morphology and Comparison of Vocabularies},
journal = {Journal of Biomolecular Structure and Dynamics},
volume = {4},
number = {1},
pages = {11-21},
year  = {1986},
}

@article{mireille,
  author    = {Mireille R{\'{e}}gnier and
               Mathias Vandenbogaert},
  title     = {Comparison of Statistical Significance Criteria},
  journal   = {J. Bioinformatics and Computational Biology},
  volume    = {4},
  number    = {2},
  pages     = {537--552},
  year      = {2006},
}

@article {almir,
	Title = {On avoided words, absent words, and their application to biological sequence analysis},
	Author = {Almirantis, Yannis and Charalampopoulos, Panagiotis and Gao, Jia and Iliopoulos, Costas S and Mohamed, Manal and Pissis, Solon P and Polychronopoulos, Dimitris},
	Volume = {12},
	Year = {2017},
	Journal = {Algorithms for molecular biology : AMB},
}

@article{regex,
title = "Approximate matching of regular expressions",
journal = "Bulletin of Mathematical Biology",
volume = "51",
number = "1",
pages = "5--37",
year = "1989",
issn = "0092-8240",
author = "Eugene W. Myers and Webb Miller"
}

@book{charubook,
author={C. C. Aggarwal and P. S. Yu},
title={Privacy-Preserving Data Mining: Models and Algorithms},
year={2008},
publisher={Springer},
}

@book{bonchibook,
title={Privacy-Aware Knowledge Discovery: Novel Applications and New Techniques},
author={F. Bonchi and E. Ferrari},
year={2010},
publisher={CRC Press}
}

@article{verykios,
 author = {V. S. Verykios and A. K. Elmagarmid and E. Bertino and Y. Saygin and E. Dasseni},
 title = {Association Rule Hiding},
 journal = {TKDE},
 volume = {16},
 number = {4},
 year = {2004},
 pages = {434--447},
 }
 
 @article{anna,
 author = {A. Monreale and D. Pedreschi and R. G. Pensa and F. Pinelli},
 title = {Anonymity Preserving Sequential Pattern Mining},
 journal = {Artif. Intell. Law},
 volume = {22},
 number = {2},
 year = {2014},
 pages = {141--173},
 }
 
 @InProceedings{differentialprivacy,
author="C. Dwork and F. McSherry and K. Nissim and A. Smith",
title="Calibrating Noise to Sensitivity in Private Data Analysis",
booktitle="3rd TCC",
year="2006",
pages="265--284",
}

 @incollection{encyclopaedia,
  author    = {Sara Foresti},
  title     = {Microdata Protection},
  booktitle = {Encyclopedia of Cryptography and Security, 2nd Ed},
  pages     = {781--783},
  publisher = {Springer},
  year      = {2011},
  timestamp = {Wed, 12 Jul 2017 09:11:26 +0200},
  biburl    = {https://dblp.org/rec/reference/crypt/Foresti11a.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{xukdd08,
  author    = {Y. Xu and
               K. Wang and
               A. W. Fu and
               P. S. Yu},
  title     = {Anonymizing transaction databases for publication},
  booktitle = {24th KDD},
  pages     = {767--775},
  year      = {2008},
}

 @inproceedings{sunicdm,
 author = {X. Sun and P. S. Yu},
 title = {A Border-Based Approach for Hiding Sensitive Frequent Itemsets},
 booktitle = {5th ICDM},
 year = {2005},
 pages = {426--433},
 }
 
 @InProceedings{natwichai,
author="J. Natwichai and X. Li and M. Orlowska",
title="Hiding Classification Rules for Data Sharing with Privacy Preservation",
booktitle="7th DaWaK",
year="2005",
pages="468--477"
}

@inproceedings{samaratipods,
  author    = {P. Samarati and
               L. Sweeney},
  title     = {Generalizing Data to Provide Anonymity when Disclosing Information (Abstract)},
  booktitle = {17th PODS},
  pages     = {188},
  year      = {1998},
}

@incollection{abulchapter,
author={Osman Abul},
title={Knowledge hiding in emerging application domains},
booktitle={Privacy-Aware Knowledge Discovery: Novel Applications and New Techniques},
year={2010},
publisher={CRC Press}
}

@article{fungacmsurv,
author = {Fung, Benjamin C. M. and Wang, Ke and Chen, Rui and Yu, Philip S.},
title = {Privacy-Preserving Data Publishing: A Survey of Recent Developments},
year = {2010},
publisher = {Association for Computing Machinery},
volume = {42},
number = {4},
journal = {ACM Comput. Surv.},
articleno = {14},
numpages = {53},
}

@inproceedings{charusdm,
author = {C. C. Aggarwal and P. S. Yu},
title = {On Anonymization of String Data},
booktitle = {7th SDM},
pages = {419--424},
year={2007},
}

@book{manningbook,
author = {Manning, Christopher D. and Sch\"{u}tze, Hinrich},
title = {Foundations of Statistical Natural Language Processing},
year = {1999},
isbn = {0262133601},
publisher = {MIT Press},
address = {Cambridge, MA, USA}
}

@article{Pissinger,
title = {A minimal algorithm for the multiple-choice knapsack problem},
author={D. Pissinger},
journal = {Eur J Oper Res},
volume = {83},
number = {2},
pages = {394--410},
year = {1995},
}

@article{mckp,
Author = {P. Sinha and A. A. Zoltners},
Journal = {Operations Research},
Number = {3},
Pages = {431--627},
Title = {The Multiple-Choice Knapsack Problem.},
Volume = {27},
Year = {1979}
}

@book{DBLP:books/daglib/0020103,
  author    = {M. Crochemore and
               C. Hancart and
               T. Lecroq},
  title     = {Algorithms on strings},
  publisher = {Cambridge University Press},
  year      = {2007},
 }
 
 @article{DBLP:journals/jcss/GallantMS80,
  author    = {J. Gallant and
               D. Maier and
               J. A. Storer},
  title     = {On Finding Minimal Length Superstrings},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {20},
  number    = {1},
  pages     = {50--58},
  year      = {1980},
}



@INPROCEEDINGS{graham1,
author={G. Cormode and F. Korn and S. Tirthapura},
booktitle={25th ICDE},
title={Exponentially Decayed Aggregates on Data Streams},
year={2008},
pages={1379-1381},
}

  @inproceedings{indykstoc,
author = {A. Backurs and P. Indyk},
title = {Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless {SETH} is False)},
year = {2015},
booktitle = {47th STOC},
pages = {51--58},
}

@Inbook{Kellerer2004,
  author={Kellerer, Hans and Pferschy, Ulrich and Pisinger, David},
  title={The Multiple-Choice Knapsack Problem},
  booktitle={Knapsack Problems},
  year={2004},
  publisher={Springer Berlin Heidelberg},
  pages={317--347},
}

@inproceedings{IndetCPM20,
  author    = {Paweł Gawrychowski and Samah Ghazawi and Gad M. Landau},
  title     = {On Indeterminate Strings Matching},
  booktitle =	{31st CPM},
  _series    = {LIPIcs},
  _volume    = {161},
  pages     = {23:1--23:12},
  year      = {2020}
}




@article{hashing,
  author    = {Martin Dietzfelbinger and
               Anna R. Karlin and
               Kurt Mehlhorn and
               Friedhelm {Meyer auf der Heide} and
               Hans Rohnert and
               Robert Endre Tarjan},
  title     = {Dynamic Perfect Hashing: Upper and Lower Bounds},
  journal   = {{SIAM} J. Comput.},
  volume    = {23},
  number    = {4},
  pages     = {738--761},
  year      = {1994}
}

@article{sopang2,
  author    = {Aleksander Cislak and
               Szymon Grabowski},
  title     = {SOPanG 2: online searching over a pan-genome without false positives},
  journal   = {CoRR},
  volume    = {abs/2004.03033},
  year      = {2020},
  url       = {https://arxiv.org/abs/2004.03033}
}

@inproceedings{BackursI16,
  author    = {A. Backurs and
               P. Indyk},
  title     = {Which Regular Expression Patterns Are Hard to Match?},
  booktitle={57th FOCS}, 
  pages     = {457--466},
  year      = {2016}
}

@inproceedings{GawrychowskiU18,
  author    = {P. Gawrychowski and
               P. Uznanski},
  title     = {Towards Unified Approximate Pattern Matching for {Hamming} and {$L_1$} Distance},
  booktitle = {45th ICALP},
  _series    = {LIPIcs},
  _volume    = {107},
  pages     = {62:1--62:13},
  year      = {2018}
}

@book{Chazelle,
  author    = {B. Chazelle},
  title     = {The discrepancy method - randomness and complexity},
  publisher = {Cambridge University Press},
  year      = {2001}
}

@article{DBLP:journals/jacm/CrochemoreP91,
  author    = {M. Crochemore and
               D. Perrin},
  title     = {Two-Way String Matching},
  journal   = {J. {ACM}},
  volume    = {38},
  number    = {3},
  pages     = {651--675},
  year      = {1991}
  }

@inproceedings{DBLP:conf/soda/KociumakaRRW15,
  author    = {T. Kociumaka and
               J. Radoszewski and
               W. Rytter and
               T. Waleń},
  title     = {Internal Pattern Matching Queries in a Text and Applications},
  booktitle = {26th SODA},
  pages     = {532--551},
  year      = {2015}
  }

@article{DBLP:journals/siamcomp/KnuthMP77,
  author    = {D.E. Knuth and
               J.H. Morris Jr. and
               V.R. Pratt},
  title     = {Fast Pattern Matching in Strings},
  journal   = {{SIAM} J. Comput.},
  volume    = {6},
  number    = {2},
  pages     = {323--350},
  year      = {1977}
  }

@inproceedings{ruzic08constructing,
  author    = {M. Ru\v{z}i\'{c}},
  title     = {Constructing Efficient Dictionaries in Close to Sorting Time},
  booktitle = {35th ICALP},
  year      = {2008},
  pages     = {84--95},
  volume =  	 {5125},
  series =  	 {Springer LNCS}
}

@inproceedings{cpm2000,
  author    = {A. Czumaj and
               L. Gasieniec},
  title     = {On the Complexity of Determining the Period of a String},
  booktitle = {11th CPM},
  pages     = {412--422},
  year      = {2000},
   volume =  	 {1848},
  series =  	 {Springer LNCS}
}



@article{Bentley:1975:MBS:361002.361007,
 author = {J.L. Bentley},
 title = {Multidimensional Binary Search Trees Used for Associative Searching},
 journal = {Commun. ACM},
 volume = {18},
 number = {9},
 year = {1975},
 pages = {509--517}
} 

@article{DBLP:journals/jcss/SleatorT83,
  author    = {D.D. Sleator and
               R.E. Tarjan},
  title     = {A Data Structure for Dynamic Trees},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {26},
  number    = {3},
  pages     = {362--391},
  year      = {1983}
}

@inproceedings{DBLP:conf/cpm/FarachM96,
  author    = {M. Farach-Colton and
               S. Muthukrishnan},
  title     = {Perfect Hashing for Strings: formalization and Algorithms},
  booktitle = {7th CPM},
  pages     = {130--140},
  year      = {1996},
  _volume =  	 {1075},
  _series =  	 {Springer LNCS}
  }
 
@article{DBLP:journals/tcs/LarsenMNT15,
  author    = {K.G. Larsen and
               I. Munro and
               J.S. Nielsen and
               S.V. Thankachan},
  title     = {On hardness of several string indexing problems},
  journal   = {Theor. Comput. Sci.},
  volume    = {582},
  pages     = {74--82},
  year      = {2015}
  }

@inproceedings{DBLP:conf/focs/Weiner73,
  author    = {P. Weiner},
  title     = {Linear Pattern Matching Algorithms},
  booktitle = {14th SWAT/FOCS},
  pages     = {1--11},
  year      = {1973}
  }

@article{DBLP:journals/jal/AmirLP04,
  author    = {A. Amir and
               M. Lewenstein and
               E. Porat},
  title     = {Faster algorithms for string matching with $k$ mismatches},
  journal   = {J. Algorithms},
  volume    = {50},
  number    = {2},
  pages     = {257--275},
  year      = {2004}
  }

@article{FFT,
    author = {J.W. Cooley and J.W. Tukey},
    journal = {Mathematics of Computation},
    number = {90},
    pages = {297--301},
    title = {{An algorithm for the machine calculation of complex {Fourier} series}},
    volume = {19},
    year = {1965}
}

@inproceedings{KolpakovKucherov1999, 
author={R. Kolpakov and G. Kucherov},
booktitle={40th FOCS}, 
title={Finding maximal repetitions in a word in linear time}, 
year={1999}, 
pages={596-604}
}

@article{DBLP:journals/jal/Duval83,
  author    = {J.{-}P. Duval},
  title     = {Factorizing Words over an Ordered Alphabet},
  journal   = {J. Algorithms},
  volume    = {4},
  number    = {4},
  pages     = {363--381},
  year      = {1983}
  }

@article{BannaiTomohiroInenagaNakashimaTakedaTsuruta2017,
author = {Hideo Bannai and Tomohiro I and Shunsuke Inenaga and Yuto Nakashima and Masayuki Takeda and Kazuya Tsuruta},
title = {The ``Runs'' Theorem},
journal = {SIAM Journal on Computing},
volume = {46},
number = {5},
pages = {1501-1514},
year = {2017}
}


@inproceedings{isaac2011,
  author    = {T. Gagie and
               P. Gawrychowski and
               S. J. Puglisi},
  title     = {Faster Approximate Pattern Matching in Compressed Repetitive Texts},
  booktitle = {22nd ISAAC},
  pages     = {653--662},
  year      = {2011},
  volume =  	 {7074},
  series =  	 {Springer LNCS}
}

@inproceedings{soda2011,
  author    = {P. Bille and
               G. M. Landau and
               R. Raman and
               K. Sadakane and
               S. R. Satti and
               O. Weimann},
  title     = {Random Access to grammar-Compressed Strings},
  booktitle = {22nd SODA},
  pages     = {373--389},
  year      = {2011}
}

@article{jcb2009,
  author    = {N. Pisanti and
               H. Soldano and
               M. Carpentier and
               J. Pothier},
  title     = {A Relational Extension of the Notion of Motifs: Application to the Common 3D Protein Substructures Searching Problem},
  journal   = {J. of Computational Biology},
  volume    = {16},
  number    = {12},
  pages     = {1635--1660},
  year      = {2009}
}

@inproceedings{cpm2005,
  author    = {N. Pisanti and
               H. Soldano and
               M. Carpentier},
  title     = {Incremental Inference of Relational Motifs with a Degenerate Alphabet},
  booktitle = {16th CPM},
  pages     = {229--240},
   volume =  	 {3537},
  series =  	 {Springer LNCS},
  year      = {2005}
}

@inproceedings{DBLP:conf/wea/PissisR18,
  author    = {S.P. Pissis and
               A. Retha},
  title     = {Dictionary Matching in Elastic-Degenerate Texts with Applications in Searching {VCF} Files On-line},
  booktitle = {17th SEA},
  pages     = {16:1--16:14},
  year      = {2018},
   series =	{LIPIcs},
  volume =	{103}
 }


@article{IUPAC,
  author    = {{IUPAC-IUB Commission on Biochemical Nomenclature}},
  title     = {Abbreviations and symbols for nucleic acids, polynucleotides, and their constituents},
  journal   = {Biochemistry},
  volume    = {9},
  number    = {20},
  pages     = {4022--4027},
  year      = {1970}
}

@article{DBLP:journals/spe/Navarro01,
  author    = {G. Navarro},
  title     = {NR-grep: a fast and flexible pattern-matching tool},
  journal   = {Softw., Pract. Exper.},
  volume    = {31},
  number    = {13},
  pages     = {1265--1312},
  year      = {2001}
}

@INPROCEEDINGS{agrep,
    author = {S. Wu and U. Manber},
    title = {Agrep -- A Fast Approximate Pattern-Matching Tool},
    booktitle = {USENIX Technical Conference},
    year = {1992},
    pages = {153--162}
}

@inproceedings{DBLP:conf/esa/RodittyZ04,
  author    = {L. Roditty and
               U. Zwick},
  title     = {On Dynamic Shortest Paths Problems},
  booktitle = {12th ESA},
  pages     = {580--591},
   _volume =  	 {3221},
  _series =  	 {Springer LNCS},
  year      = {2004}
  }



@article{Abrahamson:1987:GSM:37185.37191,
 author = {K. Abrahamson},
 title = {Generalized String Matching},
 journal = {SIAM J. Comput.},
 volume = {16},
 number = {6},
 year = {1987},
 pages = {1039--1051}
 }

@inproceedings{DBLP:conf/focs/AbboudW14,
  author    = {A. Abboud and
               V.V. Williams},
  title     = {Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems},
  booktitle = {55th FOCS},
  pages     = {434--443},
  year      = {2014}
  }


@article{Lee:2002:FCG:505241.505242,
 author = {L. Lee},
 title = {Fast Context-free Grammar Parsing Requires Fast Boolean Matrix Multiplication},
 journal = {J. {ACM}},
 volume = {49},
 number = {1},
 year = {2002},
 pages = {1--15}
} 


@inproceedings{DBLP:conf/stoc/ColeH02,
  author    = {R. Cole and
               R. Hariharan},
  title     = {Verifying candidate matches in sparse and wildcard matching},
  booktitle = {34th STOC},
  pages     = {592--601},
  year      = {2002}
  }


@inproceedings{Chatterjee:2017,
 author = {K. Chatterjee and B. Choudhary and A. Pavlogiannis},
 title = {Optimal {Dyck} Reachability for Data-dependence and Alias Analysis},
  booktitle = {45th POPL},
 year = {2018},
 pages = {30:1--30:30}
 } 



@article{DBLP:journals/ipl/CliffordC07,
  author    = {P. Clifford and
               R. Clifford},
  title     = {Simple deterministic wildcard matching},
  journal   = {Inf. Process. Lett.},
  volume    = {101},
  number    = {2},
  pages     = {53--54},
  year      = {2007}
  }

@InProceedings{kopelowitz_et_al:2016,
  author =	{T. Kopelowitz and R. Krauthgamer},
  title =	{{Color-distance oracles and snippets}},
  booktitle =	{27th CPM},
  pages =	{24:1--24:10},
  _series =	{LIPIcs},
  year =	{2016},
  volume =	{54}
}


@inproceedings{DBLP:conf/soda/Kalai02a,
  author    = {A. Kalai},
  title     = {Efficient pattern-matching with don't cares},
  booktitle = {13th SODA},
  pages     = {655--656},
  year      = {2002}
  }


@inproceedings{Henzinger:2015,
 author = {M. Henzinger and S. Krinninger and D. Nanongkai and T. Saranurak},
 title = {Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture},
 booktitle = {47th STOC},
 year = {2015},
 pages = {21--30}
} 

@inproceedings{DBLP:conf/focs/Indyk98a,
  author    = {P. Indyk},
  title     = {Faster Algorithms for String Matching Problems: Matching the Convolution Bound},
  booktitle = {39th FOCS},
  pages     = {166--173},
  year      = {1998}
  }


@article{PeriodicityLemma,
	Author = {N.J. Fine and H.S. Wilf},
	Journal = {Proceedings of the American Mathematical Society},
	Number = {1},
	Pages = {109--114},
	Title = {Uniqueness Theorems for Periodic Functions},
	Volume = {16},
	Year = {1965}
}

@inproceedings{Fischer-Paterson,
 author = {M.J. Fischer and M.S. Paterson},
 title = {String matching and other products},
 booktitle = {7th SIAM-AMS Complexity of Computation},
 year = {1974},
 pages = {113--125}
}

@inproceedings{Chan:2015:SUF:2722129.2722145,
 author = {T.M. Chan},
 title = {Speeding Up the Four {Russians} Algorithm by About One More Logarithmic Factor},
 booktitle = {26th SODA},
 year = {2015},
 pages = {212--217},
 }

@article{Furman,
 author = {M.E. Furman}, 
 title  = {Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph},
 journal = {Soviet Mathematics Doklady},
 number = {5},
 volume = {11},
 pages = {1252},
 year = {1970}
}

@Article{Frieze1999,
author= {A. Frieze and R. Kannan},
title={Quick Approximation to Matrices and Applications},
journal={Combinatorica},
year={1999},
volume={19},
number={2},
pages={175--220}
}

@article{Munro:1971:EDT:2598952.2599354,
 author = {I. Munro},
 title = {Efficient Determination of the Transitive Closure of a Directed Graph},
 journal = {Inf. Process. Lett.},
 volume = {1},
 number = {2},
 year = {1971},
 pages = {56--58}
}


@inproceedings{Bansal:2009:RLC:1747597.1748007,
 author = {N. Bansal and R. Williams},
 title = {Regularity Lemmas and Combinatorial Algorithms},
 booktitle = {50th FOCS},
 year = {2009},
 pages = {745--754}
}

@article{Arlazaroff:Economical,
    author = {V.L. Arlazarov and E.A. Dinic and M.A. Kronrod and I.A. Farad{\v{z}}ev},
    journal = {Soviet Mathematics Doklady},
    number = {5},
    pages = {1209--1210},
    title = {{On economical construction of the transitive closure of a directed graph}},
    volume = {11},
    year = {1970}
}

@inproceedings{Fischer:1971:BMM:1446293.1446319,
 author = {M.J. Fischer and A.R. Meyer},
 title = {Boolean Matrix Multiplication and Transitive Closure},
 booktitle = {12th SWAT/FOCS},
 year = {1971},
 pages = {129--131}
} 

%xxx
@inproceedings{AbboudBW15a,
  author    = {A. Abboud and
               A. Backurs and
               V.V. Williams},
  title     = {If the Current Clique Algorithms are Optimal, So is {Valiant}'s Parser},
  booktitle={56th FOCS}, 
  pages     = {98--117},
  year      = {2015}
}

@inproceedings{Chang16,
  author    = {Y.-J. Chang},
  title     = {Hardness of {RNA} Folding Problem With Four Symbols},
  booktitle = {27th CPM},
  _series    = {LIPIcs},
  _volume    = {54},
  pages     = {13:1--13:12},
  year      = {2016}
}

@inproceedings{BringmannGSW16,
  author    = {K. Bringmann and
               F. Grandoni and
               B. Saha and
               V.V. Williams},
  title     = {Truly Sub-cubic Algorithms for Language Edit Distance and {RNA}-Folding
               via Fast Bounded-Difference Min-Plus Product},
  booktitle={56th FOCS}, 
  pages     = {375--384},
  year      = {2016}
}

@article{Valiant:1975:GCR:1739932.1740048,
 author = {L.G. Valiant},
 title = {General Context-free Recognition in Less Than Cubic Time},
 journal = {J. Comput. Syst. Sci.},
 volume = {10},
 number = {2},
 month = apr,
 year = {1975},
 pages = {308--315}
} 

@inproceedings{Itai:1977:FMC:800105.803390,
 author = {A. Itai and M. Rodeh},
 title = {Finding a Minimum Circuit in a Graph},
 booktitle = {9th STOC},
 year = {1977},
 pages = {1--10}
} 

@book{probmethod,
	Author = {N. Alon and J.H. Spencer},
	Publisher = {J. Wiley \& Sons},
	Title = {The Probabilistic Method},
	Year = 2000}

@inproceedings{williams2010subcubic,
  author={V.V. Williams and R. Williams},
  title={Subcubic equivalences between path, matrix and triangle problems},
booktitle={51st FOCS},
  pages={645--654},
  year={2010}
}

@inproceedings{Yuicalp,
  author    = {H. Yu},
  title     = {An Improved Combinatorial Algorithm for Boolean Matrix Multiplication},
  booktitle = {42nd ICALP},
  pages     = {1094--1105},
  year      = {2015},
  series =	{Springer LNCS},
   volume = {9134}
}




@article{YU2018240,
  author    = {H. Yu},
  title     = {An improved combinatorial algorithm for boolean matrix multiplication},
  journal   = {Inf. Comput.},
  volume    = {261},
  number    = {Part},
  pages     = {240--247},
  year      = {2018}
  }



@inproceedings{BringmannGL17,
author    = {K. Bringmann and
               A. Gr{\o}nlund and
               K.G. Larsen},
  title     = {A Dichotomy for Regular Expression Membership Testing},
  booktitle = {58th FOCS},
  pages     = {307--318},
  year      = {2017}
  }


@inproceedings{DBLP:conf/issac/Gall14a,
  author    = {Le Gall, Francois},
  title     = {Powers of tensors and fast matrix multiplication},
  booktitle = {39th ISSAC},
  pages     = {296--303},
  year      = {2014}
}

@article{ShiloachV82,
  author    = {Yossi Shiloach and
               Uzi Vishkin},
  title     = {An $O(\log n)$ Parallel Connectivity Algorithm},
  journal   = {J. Algorithms},
  volume    = {3},
  number    = {1},
  pages     = {57--67},
  year      = {1982}
}

@INPROCEEDINGS{BringmannGrønlundLarsen2017, 
author={K. Bringmann and A. Grønlund and K.G. Larsen}, 
booktitle={58th FOCS}, 
title={A Dichotomy for Regular Expression Membership Testing}, 
year={2017}, 
pages={307-318}
}

@article{Matousek91,
  author    = {J. Matou{\v{s}}ek},
  title     = {Computing Dominances in {$E^n$}},
  journal   = {Inf. Process. Lett.},
  volume    = {38},
  number    = {5},
  pages     = {277--278},
  year      = {1991}
}

@article{CzumajL09,
  author    = {A. Czumaj and A. Lingas},
  title     = {Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication},
  journal   = {{SIAM} J. Comput.},
  volume    = {39},
  number    = {2},
  pages     = {431--444},
  year      = {2009}
}

@inproceedings{VassilevskaW06,
  author    = {V.V. Williams and
               R. Williams},
  title     = {Finding a maximum weight triangle in $n^{3-\delta}$ time, with applications},
 booktitle = {38th STOC},
  pages     = {225--231},
  year      = {2006}
}

@article{Zwick02,
  author    = {U. Zwick},
  title     = {All pairs shortest paths using bridging sets and rectangular matrix multiplication},
  journal   = {J. {ACM}},
  volume    = {49},
  number    = {3},
  pages     = {289--317},
  year      = {2002}
}

@inproceedings{makinen2020linear,
  title={Linear Time Construction of Indexable Founder Block Graphs},
  author={M{\"a}kinen, Veli and Cazaux, Bastien and Equi, Massimo and Norri, Tuukka and Tomescu, Alexandru I},
  booktitle={20th WABI},
  _series =	{LIPIcs},
  pages =	{7:1--7:18},
  _volume = {172},
  year={2020},
}

@article{truncatedsuffixtree,
author = "Joong Chae Na and Alberto Apostolico and Costas S. Iliopoulos and Kunsoo Park",
title = "Truncated suffix trees and their application to data compression",
journal = "Theoretical Computer Science",
volume = "304",
number = "1",
pages = "87--101",
year = "2003",
}

@Article{Fredman:1984:SST:828.1884,
  author     = {Fredman, Michael L. and Koml\'{o}s, J\'{a}nos and Szemer{\'e}di, Endre},
  title      = {Storing a Sparse Table with {$\mathcal{O}(1)$} Worst Case Access Time},
  journal    = {Journal of the ACM},
  year       = {1984},
  volume     = {31},
  number     = {3},
  pages      = {538--544},
  doi        = {10.1145/828.1884},
  numpages   = {7},
  publisher  = {ACM},
}

@article{panosJEA,
author = {Charalampopoulos, Panagiotis and Iliopoulos, Costas S. and Liu, Chang and Pissis, Solon P.},
title = {Property Suffix Array with Applications in Indexing Weighted Sequences},
year = {2020},
publisher = {Association for Computing Machinery},
volume = {25},
number = {1},
journal = {ACM J. Exp. Algorithmics},
articleno = {1.8},
numpages = {16},
}

 @article{DBLP:journals/jct/KarhumakiSZ13,
  author    = {Juhani Karhum{\"{a}}ki and
               Aleksi Saarela and
               Luca Q. Zamboni},
  title     = {On a generalization of Abelian equivalence and complexity of infinite
               words},
  journal   = {Journal of Combinatorial Theory, Series {A}},
  volume    = {120},
  number    = {8},
  pages     = {2189--2206},
  year      = {2013},
}

@Article{kingsford10,
author="Kingsford, Carl
and Schatz, Michael C.
and Pop, Mihai",
title="Assembly complexity of prokaryotic genomes using short reads",
journal="BMC Bioinformatics",
year="2010",
volume="11",
number="1",
pages="21",
}

@article{Hutch75,
 author = {Hutchinson, Joan P.},
 title = {On words with prescribed overlapping subsequences},
 journal = {Utilitas Mathematica},
 volume = {7},
 year = {1975},
 pages = {241--250},
 }

 @article{DBLP:journals/tcs/KarhumakiPRW17,
  author    = {Juhani Karhum{\"{a}}ki and
               Svetlana Puzynina and
               Micha{\"{e}}l Rao and
               Markus A. Whiteland},
  title     = {On cardinalities of k-abelian equivalence classes},
  journal   = {Theoretical Computer Sciene},
  volume    = {658},
  pages     = {190--204},
  year      = {2017},
} 
 
 @article{DBLP:journals/jcss/CazauxLR19,
  author    = {Bastien Cazaux and
               Thierry Lecroq and
               Eric Rivals},
  title     = {Linking indexing data structures to de Bruijn graphs: Construction
               and update},
  journal   = {Journal of Computer and System  Sciences},
  volume    = {104},
  pages     = {165--183},
  year      = {2019},
}

@article{10.2307/2005828,
 author = {James R. Bunch and John E. Hopcroft},
 journal = {Mathematics of Computation},
 number = {125},
 pages = {231--236},
 publisher = {American Mathematical Society},
 title = {Triangular Factorization and Inversion by Fast Matrix Multiplication},
 volume = {28},
 year = {1974}
}

@book{DBLP:books/lib/Knuth98,
  author    = {Donald Ervin Knuth},
  title     = {The art of computer programming, Volume {II:} Seminumerical Algorithms,
               3rd Edition},
  publisher = {Addison-Wesley},
  year      = {1998}
}

@book{gradshteyn2007,
  author = {Gradshteyn, Izrail S. and Ryzhik, Iosif M.},
  edition = {Seventh},
  pages = {xlviii+1171},
  publisher = {Elsevier/Academic Press, Amsterdam},
  title = {Table of integrals, series, and products},
  year = 2007
}

@article{DBLP:journals/jal/ColbournMN96,
  author    = {Charles J. Colbourn and
               Wendy J. Myrvold and
               Eugene Neufeld},
  title     = {Two Algorithms for Unranking Arborescences},
  journal   = {Journal of Algorithms},
  volume    = {20},
  number    = {2},
  pages     = {268--281},
  year      = {1996},
}

@inproceedings{Williams18,
    author    = {Virginia Vassilevska Williams},
    title = {On some fine-grained questions in algorithms and complexity},
    booktitle = {International Congress of Mathematicians},
    year = {2018}
}

@inproceedings{AbboudGIKPTUW19,
  author    = {Amir Abboud and
               Loukas Georgiadis and
               Giuseppe F. Italiano and
               Robert Krauthgamer and
               Nikos Parotsidis and
               Ohad Trabelsi and
               Przemyslaw Uznanski and
               Daniel Wolleb{-}Graf},
  title     = {Faster Algorithms for All-Pairs Bounded Min-Cuts},
  booktitle = {46th ICALP},
  pages     = {7:1--7:15},
  year      = {2019}
}

@inproceedings{liu2019faster,
    title={Faster Energy Maximization for Faster Maximum Flow},
    author={Yang P. Liu and Aaron Sidford},
    year={2020},
    booktitle={52nd STOC},
    pages={803--814},
}

@inproceedings{AbboudKT20,
  author    = {Amir Abboud and
               Robert Krauthgamer and
               Ohad Trabelsi},
  title     = {New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected
               Graphs},
  booktitle = {31st SODA},
  pages     = {48--61},
  year      = {2020}
}

@article{KrauthgamerT18,
  author    = {Robert Krauthgamer and
               Ohad Trabelsi},
  title     = {Conditional Lower Bounds for All-Pairs Max-Flow},
  journal   = {{ACM} Trans. Algorithms},
  volume    = {14},
  number    = {4},
  pages     = {42:1--42:15},
  year      = {2018}
}

@article{HopcroftK73,
  author    = {John E. Hopcroft and
               Richard M. Karp},
  title     = {An $n^{2.5}$ Algorithm for Maximum Matchings in Bipartite Graphs},
  journal   = {{SIAM} J. Comput.},
  volume    = {2},
  number    = {4},
  pages     = {225--231},
  year      = {1973}
}

@book{Aho,
  author    = {Alfred V. Aho and
               John E. Hopcroft and
               Jeffrey D. Ullman},
  title     = {The Design and Analysis of Computer Algorithms},
  publisher = {Addison-Wesley},
  year      = {1974}
}

@article{decomposition,
  author    = {Ming{-}Yang Kao and
               Tak Wah Lam and
               Wing{-}Kin Sung and
               Hing{-}Fung Ting},
  title     = {A Decomposition Theorem for Maximum Weight Bipartite Matchings},
  journal   = {{SIAM} J. Comput.},
  volume    = {31},
  number    = {1},
  pages     = {18--26},
  year      = {2001}
}

@inproceedings{Moore91,
  author    = {Robert S. Boyer and
               J. Strother Moore},
  title     = {{MJRTY:} {A} Fast Majority Vote Algorithm},
  booktitle = {Automated Reasoning: Essays in Honor of Woody Bledsoe},
  _series    = {Automated Reasoning Series},
  pages     = {105--118},
  _publisher = {Kluwer Academic Publishers},
  year      = {1991}
}

@inproceedings{Madry13,
  author    = {Aleksander Mądry},
  title     = {Navigating Central Path with Electrical Flows: From Flows to Matchings,
               and Back},
  booktitle = {54th FOCS},
  pages     = {253--262},
  year      = {2013}
}

@article{gray2009language,
  title={Language phylogenies reveal expansion pulses and pauses in Pacific settlement},
  author={Gray, Russell D and Drummond, Alexei J and Greenhill, Simon J},
  journal={Science},
  volume={323},
  number={5913},
  pages={479--483},
  year={2009},
  publisher={American Association for the Advancement of Science}
}

@article{walker2012cultural,
  title={Cultural phylogenetics of the Tupi language family in lowland South America},
  author={Walker, Robert S and Wichmann, S{\o}ren and Mailund, Thomas and Atkisson, Curtis J},
  journal={PLOS One},
  volume={7},
  number={4},
  year={2012},
  publisher={Public Library of Science}
}

@article{nakhleh2005comparison,
  title={A comparison of phylogenetic reconstruction methods on an Indo-European dataset},
  author={Nakhleh, Luay and Warnow, Tandy and Ringe, Don and Evans, Steven N},
  journal={Transactions of the Philological Society},
  volume={103},
  number={2},
  pages={171--192},
  year={2005},
  publisher={Wiley Online Library}
}

@article{buneman1971recovery,
  title={The recovery of trees from measures of dissimilarity},
  author={Buneman, Peter},
  journal={Mathematics in the Archaeological and Historical Sciences},
  year={1971},
  publisher={Edinburgh University Press}
}

@article{jiao2014inferring,
  title={Inferring clonal evolution of tumors from single nucleotide somatic mutations},
  author={Jiao, Wei and Vembu, Shankar and Deshwar, Amit G and Stein, Lincoln and Morris, Quaid},
  journal={BMC bioinformatics},
  volume={15},
  number={1},
  pages={35},
  year={2014},
  publisher={Springer}
}

@article{malikic2019phiscs,
  title={PhISCS: a combinatorial approach for subperfect tumor phylogeny reconstruction via integrative use of single-cell and bulk sequencing data},
  author={Malikic, Salem and Mehrabadi, Farid Rashidi and Ciccolella, Simone and Rahman, Md Khaledur and Ricketts, Camir and Haghshenas, Ehsan and Seidman, Daniel and Hach, Faraz and Hajirasouliha, Iman and Sahinalp, S Cenk},
  journal={Genome Research},
  volume={29},
  number={11},
  pages={1860--1877},
  year={2019},
  publisher={Cold Spring Harbor Lab}
}

@article{huber2006phylogenetic,
  title={Phylogenetic networks from multi-labelled trees},
  author={Huber, Katharina T. and Moulton, Vincent},
  journal={Journal of Mathematical Biology},
  volume={52},
  number={5},
  pages={613--632},
  year={2006},
  publisher={Springer}
}

@article{huson2006application,
  title={Application of phylogenetic networks in evolutionary studies},
  author={Huson, Daniel H and Bryant, David},
  journal={Molecular Biology and Evolution},
  volume={23},
  number={2},
  pages={254--267},
  year={2006},
  publisher={Oxford University Press}
}

@article{chor2005maximum,
  title={Maximum likelihood of evolutionary trees: hardness and approximation},
  author={Chor, Benny and Tuller, Tamir},
  journal={Bioinformatics},
  volume={21},
  number={suppl\_1},
  pages={i97--i106},
  year={2005},
  publisher={Oxford University Press}
}

@article{farris1970methods,
  title={Methods for computing Wagner trees},
  author={Farris, James S},
  journal={Systematic Biology},
  volume={19},
  number={1},
  pages={83--92},
  year={1970},
  publisher={Society of Systematic Zoology}
}

@book{felsenstein2004inferring,
  title={Inferring phylogenies},
  author={Felsenstein, Joseph and Felenstein, Joseph},
  volume={2},
  year={2004},
  publisher={Sinauer Associates Sunderland, MA}
}

@inproceedings{DBLP:conf/icalp/GawrychowskiLSW18,
  author    = {Pawel Gawrychowski and
               Gad M. Landau and
               Wing{-}Kin Sung and
               Oren Weimann},
  title     = {A Faster Construction of Greedy Consensus Trees},
  booktitle = {45th ICALP},
  pages     = {63:1--63:14},
  year      = {2018}
}

@article{bryant2003classification,
  title={A classification of consensus methods for phylogenetics},
  author={Bryant, David},
  journal={DIMACS Series in Discrete Mathematics and Theoretical Computer Science},
  volume={61},
  pages={163--184},
  year={2003},
  publisher={American Mathematical Society}
}

@article{jansson2016improved,
  title={Improved algorithms for constructing consensus trees},
  author={Jansson, Jesper and Shen, Chuanqi and Sung, Wing-Kin},
  journal={Journal of the ACM},
  volume={63},
  number={3},
  pages={1--24},
  year={2016},
  publisher={ACM New York, NY, USA}
}

@article{jansson2016algorithms,
  title={Algorithms for the majority rule (+) consensus tree and the frequency difference consensus tree},
  author={Jansson, Jesper and Rajaby, Ramesh and Shen, Chuanqi and Sung, Wing-Kin},
  journal={{IEEE/ACM} Trans. Comput. Biology Bioinform.},
  volume={15},
  number={1},
  pages={15--26},
  year={2016},
  publisher={IEEE}
}

@incollection{dobson1975comparing,
  title={Comparing the shapes of trees},
  author={Dobson, Annette J},
  booktitle={Combinatorial Mathematics III},
  pages={95--100},
  year={1975},
  publisher={Springer}
}

@article{estabrook1985comparison,
  title={Comparison of undirected phylogenetic trees based on subtrees of four evolutionary units},
  author={Estabrook, George F and McMorris, FR and Meacham, Christopher A},
  journal={Systematic Zoology},
  volume={34},
  number={2},
  pages={193--200},
  year={1985},
  publisher={Society of Systematic Zoology}
}

@inproceedings{dudek2019computing,
  title={Computing quartet distance is equivalent to counting 4-cycles},
  author={Dudek, Bart{\l}omiej and Gawrychowski, Pawe{\l}},
  booktitle={51st STOC},
  pages={733--743},
  year={2019}
}

@incollection{robinson1979comparison,
  title={Comparison of weighted labelled trees},
  author={Robinson, David F and Foulds, Leslie R},
  booktitle={Combinatorial Mathematics VI},
  pages={119--126},
  year={1979},
  publisher={Springer}
}

@article{robinson1981comparison,
  title={Comparison of phylogenetic trees},
  author={Robinson, David F and Foulds, Leslie R},
  journal={Mathematical Biosciences},
  volume={53},
  number={1-2},
  pages={131--147},
  year={1981},
  publisher={Elsevier}
}

@inproceedings{brodal2013efficient,
  title={Efficient algorithms for computing the triplet and quartet distance between trees of arbitrary degree},
  author={Brodal, Gerth St{\o}lting and Fagerberg, Rolf and Mailund, Thomas and Pedersen, Christian NS and Sand, Andreas},
  booktitle={24th SODA},
  pages={1814--1832},
  year={2013},
}

@inproceedings{dasgupta1997distances,
  title={On distances between phylogenetic trees},
  author={DasGupta, Bhaskar and He, Xin and Jiang, Tao and Li, Ming and Tromp, John and Zhang, Louxin},
  booktitle={8th SODA},
  pages={427--436},
  year={1997}
}

@article{bordewich2005computational,
  title={On the computational complexity of the rooted subtree prune and regraft distance},
  author={Bordewich, Magnus and Semple, Charles},
  journal={Annals of Combinatorics},
  volume={8},
  number={4},
  pages={409--423},
  year={2005},
  publisher={Springer}
}

@article{allen2001subtree,
  title={Subtree transfer operations and their induced metrics on evolutionary trees},
  author={Allen, Benjamin L and Steel, Mike},
  journal={Annals of Combinatorics},
  volume={5},
  number={1},
  pages={1--15},
  year={2001},
  publisher={Springer}
}

@article{hajirasouliha2014combinatorial,
  title={A combinatorial approach for analyzing intra-tumor heterogeneity from high-throughput sequencing data},
  author={Hajirasouliha, Iman and Mahmoody, Ahmad and Raphael, Benjamin J},
  journal={Bioinformatics},
  volume={30},
  number={12},
  pages={i78--i86},
  year={2014},
  publisher={Oxford University Press}
}

@article{nowell1976clonal,
  title={The clonal evolution of tumor cell populations},
  author={Nowell, Peter C},
  journal={Science},
  volume={194},
  number={4260},
  pages={23--28},
  year={1976},
  publisher={American Association for the Advancement of Science}
}

@article{yuan2015bitphylogeny,
  title={BitPhylogeny: a probabilistic framework for reconstructing intra-tumor phylogenies},
  author={Yuan, Ke and Sakoparnig, Thomas and Markowetz, Florian and Beerenwinkel, Niko},
  journal={Genome Biology},
  volume={16},
  number={1},
  pages={36},
  year={2015},
  publisher={BioMed Central}
}

@article{bonizzoni2018does,
  title={Does relaxing the infinite sites assumption give better tumor phylogenies? An ILP-based comparative approach},
  author={Bonizzoni, Paola and Ciccolella, Simone and Della Vedova, Gianluca and Soto, Mauricio},
  journal={{IEEE/ACM} Trans. Comput. Biology Bioinform.},
  volume={16},
  number={5},
  pages={1410--1423},
  year={2018},
  publisher={IEEE}
}

@inproceedings{bonizzoni2017beyond,
  title={Beyond perfect phylogeny: Multisample phylogeny reconstruction via ilp},
  author={Bonizzoni, Paola and Ciccolella, Simone and Della Vedova, Gianluca and Soto, Mauricio},
  booktitle={8th ACM-BCB},
  pages={1--10},
  year={2017}
}

@article{tai1979tree,
  title={The tree-to-tree correction problem},
  author={Tai, Kuo-Chung},
  journal={Journal of the ACM},
  volume={26},
  number={3},
  pages={422--433},
  year={1979},
  publisher={ACM New York, NY, USA}
}

@article{zhang1989simple,
  title={Simple fast algorithms for the editing distance between trees and related problems},
  author={Zhang, Kaizhong and Shasha, Dennis},
  journal={{SIAM} J. Comput.},
  volume={18},
  number={6},
  pages={1245--1262},
  year={1989},
  publisher={SIAM}
}

@article{mcvicar2016sumoted,
  title={SuMoTED: An intuitive edit distance between rooted unordered uniquely-labelled trees},
  author={McVicar, Matt and Sach, Benjamin and Mesnage, C{\'e}dric and Lijffijt, Jefrey and Spyropoulou, Eirini and De Bie, Tijl},
  journal={Pattern Recognition Letters},
  volume={79},
  pages={52--59},
  year={2016},
  publisher={Elsevier}
}

@article{pawlik2015efficient,
  title={Efficient computation of the tree edit distance},
  author={Pawlik, Mateusz and Augsten, Nikolaus},
  journal={ACM Transactions on Database Systems},
  volume={40},
  number={1},
  pages={1--40},
  year={2015},
  publisher={ACM New York, NY, USA}
}

9@inproceedings{govek2018consensus,
  title={A consensus approach to infer tumor evolutionary histories},
  author={Govek, Kiya and Sikes, Camden and Oesper, Layla},
  booktitle={9th BCB},
  pages={63--72},
  year={2018}
}

@book{steel2016phylogeny,
  title={Phylogeny: discrete and random processes in evolution},
  author={Steel, Mike},
  year={2016},
  publisher={SIAM}
}

@book{gusfield2014recombinatorics,
  title={ReCombinatorics: the algorithmics of ancestral recombination graphs and explicit phylogenetic networks},
  author={Gusfield, Dan},
  year={2014},
  publisher={MIT press}
}

@article{DiNardo2019,
    author = {DiNardo, Zach and Tomlinson, Kiran and Ritz, Anna and Oesper, Layla},
    title = "{Distance measures for tumor evolutionary trees}",
    journal = {Bioinformatics},
    year = {2019},
}

@article{liu2020faster,
  title={Faster Divergence Maximization for Faster Maximum Flow},
  author={Liu, Yang P and Sidford, Aaron},
  journal={arXiv preprint arXiv:2003.08929},
  year={2020}
}

@article{Bioinfo2020,
    author = {Ciccolella, Simone and Bernardini, Giulia and Denti, Luca and Bonizzoni, Paola and Previtali, Marco and Della Vedova, Gianluca},
    title = "{Triplet-based similarity score for fully multilabeled trees with poly-occurring labels}",
    journal = {Bioinformatics},
    year = {2020},
}

@book{semple2003phylogenetics,
  title={Phylogenetics},
  author={Semple, Charles and Steel, Mike and others},
  volume={24},
  year={2003},
  publisher={Oxford University Press on Demand}
}

@incollection{karp1972reducibility,
  title={Reducibility among combinatorial problems},
  author={Karp, Richard M},
  booktitle={Complexity of computer computations},
  pages={85--103},
  year={1972},
  publisher={Springer}
}

@inproceedings{jiang-2015-approximation,
  title={Approximation and nonapproximability for the one-sided scaffold filling problem},
  author={Jiang, Haitao and Ma, Jingjing and Luan, Junfeng and Zhu, Daming},
  booktitle={21st COCOON},
  pages={251--263},
  year={2015},
  _organization={Springer}
}

@inproceedings{spire2017,
  title={Pattern matching on elastic-degenerate text with errors},
  author={Bernardini, Giulia and Pisanti, Nadia and Pissis, Solon P and Rosone, Giovanna},
  booktitle={24th SPIRE},
  pages={74--90},
  year={2017},
  _organization={Springer}
}

@inproceedings{Maciuca2016,
  author    = {Sorina Maciuca and
               Carlos del Ojo Elias and
               Gil McVean and
               Zamin Iqbal},
  title     = {A Natural Encoding of Genetic Variation in a Burrows-Wheeler Transform
               to Enable Mapping and Genome Inference},
  booktitle = {16th WABI},
  pages     = {222--233},
  year      = {2016},
}

@article{DBLP:journals/ipl/Baeza-YatesP96,
  author    = {Ricardo A. Baeza{-}Yates and
               Chris H. Perleberg},
  title     = {Fast and Practical Approximate String Matching},
  journal   = {Inf. Process. Lett.},
  volume    = {59},
  number    = {1},
  pages     = {21--27},
  year      = {1996}
}

@article{DBLP:journals/jda/HolubSW08,
  author    = {Jan Holub and
               William F. Smyth and
               Shu Wang},
  title     = {Fast pattern-matching on indeterminate strings},
  journal   = {J. Discrete Algorithms},
  volume    = {6},
  number    = {1},
  pages     = {37--50},
  year      = {2008},
  }

@article{10002015global,
    author = {{The 1000 Genomes Project Consortium}},
    journal = {Nature},
    number = {7571},
    pages = {68--74},
    publisher = {Nature Research},
    title = {{A global reference for human genetic variation}},
    volume = {526},
    year = {2015}
}

@inproceedings{DBLP:conf/isaac/GagieGP11,
  author    = {Travis Gagie and
               Pawel Gawrychowski and
               Simon J. Puglisi},
  title     = {Faster Approximate Pattern Matching in Compressed Repetitive Texts},
  booktitle = {22nd ISAAC},
  pages     = {653--662},
  year      = {2011},
}

@inproceedings{DBLP:conf/ic3k/WandeltL12,
  author    = {Sebastian Wandelt and
               Ulf Leser},
  title     = {String Searching in Referentially Compressed Genomes},
  booktitle = {4th KDIR},
  pages     = {95--102},
  year      = {2012}
}

@ARTICLE{10.3389/fbioe.2015.00012,
AUTHOR={Gagie, Travis and Puglisi, Simon J.},   
TITLE={Searching and Indexing Genomic Databases via Kernelization},      
JOURNAL={Frontiers in Bioengineering and Biotechnology},      
VOLUME={3},      
PAGES={12},     
YEAR={2015},      
}

@article{altschul1990basic,
title = "Basic local alignment search tool",
journal = "Journal of Molecular Biology",
volume = "215",
number = "3",
pages = "403--410",
year = "1990",
author = "Stephen F. Altschul and Warren Gish and Webb Miller and Eugene W. Myers and David J. Lipman",
}



@inproceedings{DBLP:conf/iwoca/Navarro12,
  author    = {Gonzalo Navarro},
  title     = {Indexing Highly Repetitive Collections},
  booktitle = {23rd IWOCA},
  pages     = {274--279},
  year      = {2012},
}


@article{DBLP:journals/bioinformatics/RahnWR14,
  author    = {Ren{\'{e}} Rahn and
               David Weese and
               Knut Reinert},
  title     = {Journaled string tree - a scalable data structure for analyzing thousands
               of similar genomes on your laptop},
  journal   = {Bioinformatics},
  volume    = {30},
  number    = {24},
  pages     = {3499--3505},
  year      = {2014},
}

@article{uk10k2015uk10k,
  title={The UK10K project identifies rare variants in health and disease},
  author={UK10K consortium and others},
  journal={Nature},
  volume={526},
  number={7571},
  pages={82--90},
  year={2015},
  publisher={Nature Publishing Group}
}

@article{sherry2001dbsnp,
  title={dbSNP: the NCBI database of genetic variation},
  author={Sherry, Stephen T and Ward, M-H and Kholodov, M and Baker, J and Phan, Lon and Smigielski, Elizabeth M and Sirotkin, Karl},
  journal={Nucleic acids research},
  volume={29},
  number={1},
  pages={308--311},
  year={2001},
  publisher={Oxford University Press}
}

@article{sudmant2015integrated,
  title={An integrated map of structural variation in 2,504 human genomes},
  author={Sudmant, Peter H and Rausch, Tobias and Gardner, Eugene J and Handsaker, Robert E and Abyzov, Alexej and Huddleston, John and Zhang, Yan and Ye, Kai and Jun, Goo and Fritz, Markus Hsi-Yang and others},
  journal={Nature},
  volume={526},
  number={7571},
  pages={75--81},
  year={2015},
  publisher={Nature Publishing Group}
}

@article{Bille2011,
  author    = {Philip Bille and
               Gad M. Landau and
               Rajeev Raman and
               Kunihiko Sadakane and
               Srinivasa Rao Satti and
               Oren Weimann},
  title     = {Random Access to Grammar-Compressed Strings and Trees},
  journal   = {{SIAM} J. Comput.},
  volume    = {44},
  number    = {3},
  pages     = {513--539},
  year      = {2015},
}


@inproceedings{DBLP:conf/alenex/Siren17,
  author    = {Jouni Sir{\'{e}}n},
  title     = {Indexing Variation Graphs},
  booktitle = {19th ALENEX},
  pages     = {13--27},
  year      = {2017},
}

@article{DBLP:journals/tcs/NaKPLLMP16,
  author    = {Joong Chae Na and
               Hyunjoon Kim and
               Seunghwan Min and
               Heejin Park and
               Thierry Lecroq and
               Martine L{\'{e}}onard and
               Laurent Mouchard and
               Kunsoo Park},
  title     = {FM-index of alignment with gaps},
  journal   = {Theor. Comput. Sci.},
  volume    = {710},
  pages     = {148--157},
  year      = {2018},
  }

@inproceedings{Pisanti:Online,
  author    = {Roberto Grossi and
               Costas S. Iliopoulos and
               Chang Liu and
               Nadia Pisanti and
               Solon P. Pissis and
               Ahmad Retha and
               Giovanna Rosone and
               Fatima Vayani and
               Luca Versari},
  title     = {On-Line Pattern Matching on Similar Texts},
  booktitle = {28th CPM},
  pages     = {9:1--9:14},
  year      = {2017},
}


@article{DBLP:journals/bioinformatics/HuangPB13,
  author    = {Lin Huang and
               Victoria Popic and
               Serafim Batzoglou},
  title     = {Short read alignment with populations of genomes},
  journal   = {Bioinformatics},
  volume    = {29},
  number    = {13},
  pages     = {361--370},
  year      = {2013},
}

@inproceedings{Landau:Introducing,
  author    = {Gad M. Landau and
               Uzi Vishkin},
  title     = {Introducing Efficient Parallelism into Approximate String Matching
               and a New Serial Algorithm},
  booktitle = {18th STOC},
  pages     = {220--230},
  year      = {1986},
}


@inproceedings{COCOA2016,
  author    = {Carl Barton and
               Chang Liu and
               Solon P. Pissis},
  title     = {On-Line Pattern Matching on Uncertain Sequences and Applications},
  booktitle = {10th COCOA},
  pages     = {547--562},
  year      = {2016},
}


@inproceedings{ISAAC2016,
  author    = {Tomasz Kociumaka and
               Solon P. Pissis and
               Jakub Radoszewski},
  title     = {Pattern Matching and Consensus Problems on Weighted Sequences and
               Profiles},
  booktitle = {27th ISAAC},
  pages     = {46:1--46:12},
  year      = {2016},
}

@book{Stephen:string,
author={G. A. Stephen},
title={String searching algorithms},
publisher= {World Scientific Publishing Co.},
year= {1994},
address={Inc. River Edge, NJ, USA}
}

@article{pan-genome,
author    = {{The Computational Pan{-}Genomics Consortium}},
  title     = {Computational pan-genomics: status, promises and challenges},
  journal   = {Briefings in Bioinformatics},
  volume    = {19},
  number    = {1},
  pages     = {118--135},
  year      = {2018},
 }

@inproceedings{Costas:LATA,
  author    = {Costas S. Iliopoulos and
               Ritu Kundu and
               Solon P. Pissis},
  title     = {Efficient Pattern Matching in Elastic-Degenerate Texts},
  booktitle = {11th LATA},
  pages     = {131--142},
  year      = {2017},
}

@inproceedings{aoyama2018faster,
  author    = {Kotaro Aoyama and
               Yuto Nakashima and
               Tomohiro I and
               Shunsuke Inenaga and
               Hideo Bannai and
               Masayuki Takeda},
  title     = {Faster Online Elastic Degenerate String Matching},
  booktitle = {29th CPM},
  pages     = {9:1--9:10},
  year      = {2018},
}


@InProceedings{pissis_et_al:LIPIcs:2018:8951,
  author    = {Solon P. Pissis and
               Ahmad Retha},
  title     = {Dictionary Matching in Elastic-Degenerate Texts with Applications
               in Searching {VCF} Files On-line},
  booktitle = {17th SEA},
  pages     = {16:1--16:14},
  year      = {2018},
}

@article{DBLP:conf/isaac/CrochemoreIKRRW14,
  author    = {Maxime Crochemore and
               Costas S. Iliopoulos and
               Tomasz Kociumaka and
               Jakub Radoszewski and
               Wojciech Rytter and
               Tomasz Walen},
  title     = {Covering problems for partial words and for indeterminate strings},
  journal   = {Theor. Comput. Sci.},
  volume    = {698},
  pages     = {25--39},
  year      = {2017},
}

@InProceedings{iliopoulos_et_al:LIPIcs:2016:6084,
  author    = {Costas S. Iliopoulos and
               Jakub Radoszewski},
  title     = {Truly Subquadratic-Time Extension Queries and Periodicity Detection
               in Strings with Uncertainties},
  booktitle = {27th CPM},
  pages     = {8:1--8:12},
  year      = {2016}
}

@article{KMRelat,
  author    = {Nadia Pisanti and
               Henry Soldano and
               Mathilde Carpentier and
               Jo{\"{e}}l Pothier},
  title     = {A Relational Extension of the Notion of Motifs: Application to the
               Common 3D Protein Substructures Searching Problem},
  journal   = {Journal of Computational Biology},
  volume    = {16},
  number    = {12},
  pages     = {1635--1660},
  year      = {2009},
}

@article{KMRC,
  author    = {Henry Soldano and
               Alain Viari and
               Marc Champesme},
  title     = {Searching for flexible repeated patterns using a non-transitive similarity
               relation},
  journal   = {Pattern Recognition Letters},
  volume    = {16},
  number    = {3},
  pages     = {233--246},
  year      = {1995},
}

@article{10.1093/bioinformatics/btz162,
    author = {Rautiainen, Mikko and Makinen, Veli and Marschall, Tobias},
    title = "{Bit-parallel sequence-to-graph alignment}",
    journal = {Bioinformatics},
    year = {2019},
}

@article{ParameterizedComplexity,
  title={RG Downey and MR Fellows. Parameterized complexity. Monographs in computer science. Springer, New York, Berlin, and Heidelberg, 1999, xv+ 533 pp.},
  author={Flum, J{\"o}rg},
  journal={Bulletin of Symbolic Logic},
  volume={8},
  number={4},
  pages={528--529},
  year={2002},
  publisher={Cambridge University Press}
}

@article{jcb2009,
  author    = {N. Pisanti and
               H. Soldano and
               M. Carpentier and
               J. Pothier},
  title     = {A Relational Extension of the Notion of Motifs: Application to the Common 3D Protein Substructures Searching Problem},
  journal   = {Journal of Computational Biology},
  volume    = {16},
  number    = {12},
  pages     = {1635--1660},
  year      = {2009}
}

@inproceedings{cpm2005,
  author    = {N. Pisanti and
               H. Soldano and
               M. Carpentier},
  title     = {Incremental Inference of Relational Motifs with a Degenerate Alphabet},
  booktitle = {16th CPM},
  pages     = {229--240},
   volume =  	 {3537},
  series =  	 {Springer LNCS},
  year      = {2005}
}


@article{B-Y:fastApprox,
author = {R.A. Baeza-Yates and C.H. Perleberg},
title={Fast and practical approximate string match},
journal= {ing. Inf. Process. Lett.},
year= {1996},
volume= {59(1)},
pages= {21-27}
}

@article{mrna,
author = {Schuh, Randall T.},
title = {Major Patterns in Vertebrate Evolution},
journal = {Systematic Biology},
volume = {27},
number = {2},
pages = {172},
year = {1978}
}

@article{aminoacid,
author = {J. A. Gally  and  G. M. Edelman},
title = {The Genetic Control of Immunoglobulin Synthesis},
journal = {Annual Review of Genetics},
volume = {6},
number = {1},
pages = {1-46},
year = {1972}
}

@article {Wuilmart,
	Title = {On the location of palindromes in immunoglobulin genes},
	Author = {Wuilmart, C. and Urbain, J. and Givol, D.},
	Number = {6},
	Volume = {74},
	Year = {1977},
	Journal = {Proceedings of the National Academy of Sciences of the United States of America},
	Pages = {2526-2530},
}


@article{DBLP:journals/eccc/GaoI16,
  author    = {Jiawei Gao and
               Russell Impagliazzo},
  title     = {Orthogonal Vectors is hard for first-order properties on sparse graphs},
  journal   = {Electronic Colloquium on Computational Complexity {(ECCC)}},
  volume    = {23},
  pages     = {53},
  year      = {2016}
}

@article{expr_net,
  author    = {Myers, Eugene W},
  title     = {Approximate Matching of Network Expressions with Spacers},
  journal   = {Journal of Computational Biology},
  volume    = {3},
  number    = {1},
  pages     = {33--51},
  year      = {1996}
}

@inproceedings{farach,
  title={Optimal suffix tree construction with large alphabets},
  author={Farach, Martin},
  booktitle={38th FOCS},
  pages={137--143},
  year={1997},
  _Publisher={IEEE}
}



@inproceedings{LCA,
author="Bender, Michael A.
and Farach-Colton, Mart{\'i}n",
title="The {LCA} Problem Revisited",
bookTitle="4th LATIN",
_series="LNCS",
year="2000",
_publisher="Springer Berlin Heidelberg",
_volume="1776",
pages="88--94"
}

@article{GD-strings-palindromes-NAR,
  author    = {Lee Ann McCue and William Thompson and Steven Carmack and Michael P. Ryan and Jun S. Liu and Victoria Derbyshire and Charles E. Lawrence},
  title     = {Phylogenetic footprinting of transcription factor binding sites in proteobacterial genomes},
  journal   = {Nucleic Acids Research},
  volume    = {29},
  number    = {3},
  pages     = {774--782},
  year      = {2001}
}

@article{GD-strings-NAR,
  author    = {Martin C. Frith and Ulla Hansen and John L. Spouge and Zhiping Weng},
  title     = {Finding functional sequence elements by multiple local alignment
},
  journal   = {Nucleic Acids Res.},
  volume    = {32},
  number    = {1},
  pages     = {189--200},
  year      = {2004}
}

@Inbook{Lipton2010,
author="Lipton, Richard J.",
title="On The Intersection of Finite Automata",
bookTitle="The P=NP Question and G{\"o}del's Lost Letter",
year="2010",
publisher="Springer US",
address="Boston, MA",
pages="145--148"
}

@inproceedings{Adamczyk2017,
author="Adamczyk, Micha{\l}
and Alzamel, Mai
and Charalampopoulos, Panagiotis
and Iliopoulos, Costas S.
and Radoszewski, Jakub",
title="Palindromic Decompositions with Gaps and Errors",
bookTitle="12th CSR",
_volume="10304",
_series="Springer LNCS",
year="2017",
pages="48--61"
}




@article{AMOB2017,
year={2017},
author="Almirantis, Yannis and Charalampopoulos, Panagiotis and Gao, Jia and Iliopoulos, Costas S. and Mohamed, Manal and Pissis, Solon P. and Polychronopoulos, Dimitris",
title={On avoided words, absent words, and their application to biological sequence analysis},
journal={Algorithms for Molecular Biology},
volume="12",
number="1",
pages="5"
}

@article{manacher1975new,
  title={A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a String},
  author={Manacher, Glenn},
  journal={Journal of the ACM},
  volume={22},
  number={3},
  pages={346--351},
  year={1975},
  publisher={ACM}
}

@article{apostolico1995parallel,
  title={Parallel detection of all palindromes in a string},
  author={Apostolico, Alberto and Breslauer, Dany and Galil, Zvi},
  journal={Theoretical Computer Science},
  volume={141},
  number={1},
  pages={163--173},
  year={1995},
  publisher={Elsevier}
}

@book{Gusfield:1997:AST:262228,
 author = {Gusfield, Dan},
 title = {Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology},
 year = {1997},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
} 

@INPROCEEDINGS{PSC2013-7, 
 author = "Ali Alatabbi and Costas S. Iliopoulos and M. Sohel Rahman",
 title = "Maximal Palindromic Factorization",
 booktitle = "18th PSC",
  year = 2013,
 pages = "70--77",
}

@article{Fici:2014:SAM:2953214.2953656,
 author = {Fici, Gabriele and Gagie, Travis and K\"{a}rkk\"{a}inen, Juha and Kempa, Dominik},
 title = {A Subquadratic Algorithm for Minimum Palindromic Factorization},
 journal = {Journal of Discrete Algorithms},
 issue_date = {September 2014},
 volume = {28},
 year = {2014},
 issn = {1570-8667},
 pages = {41--48}
}

@book{makinen2015genome,
  title={Genome-scale algorithm design},
  author={M{\"a}kinen, Veli and Belazzougui, Djamal and Cunial, Fabio and Tomescu, Alexandru I},
  year={2015},
  publisher={Cambridge University Press}
}

@inproceedings{I2014,
author="I, Tomohiro
and Sugimoto, Shiho
and Inenaga, Shunsuke
and Bannai, Hideo
and Takeda, Masayuki",
title="Computing Palindromic Factorizations and Palindromic Covers On-line",
bookTitle={25th CPM},
_series="Springer LNCS",
_volume="8486",
year="2014", 
pages="150--161"
}

@incollection{DBLP:conf/iwoca/RubinchikS15,
author="Rubinchik, Mikhail
and Shur, Arseny M.",
title="EERTREE: An Efficient Data Structure for Processing Palindromes in Strings",
bookTitle="27th IWOCA",
year="2015",
series="Springer LNCS",
volume="9538",
pages="321--333",
}

@article{muhire2014evidence,
  title={Evidence of pervasive biologically functional secondary structures within the genomes of eukaryotic single-stranded {DNA} viruses},
  author={Muhire, Brejnev Muhizi and Golden, Michael and Murrell, Ben and Lefeuvre, Pierre and Lett, Jean-Michel and Gray, Alistair and Poon, Art YF and Ngandu, Nobubelo Kwanele and Semegni, Yves and Tanov, Emil Pavlov and others},
  journal={Journal of virology},
  volume={88},
  number={4},
  pages={1972--1989},
  year={2014},
  publisher={Am Soc Microbiol}
}

@incollection{EANNb,
author={Mai Alzamel and Jia Gao and Costas S. Iliopoulos and Chang Liu and Solon P. Pissis},
year={2017},
booktitle={18th EANN},
title={Efficient Computation of Palindromes in Sequences with Uncertainties},
_series={Springer CCIS},
_volume={744},
pages={620--629}
}



%10
@article{Huan:short, 
author = {L. Huang and V. Popic and S. Batzoglou},
title={Short read alignment with populations of genomes},
journal= {Bioinformatics},
year= {2013},
volume= {29(13)},
pages= {361-370}
}


@book{Stephen:string,
author={G. A. Stephen},
title={String searching algorithms},
publisher= {World Scientific Publishing Co.},
year= {1994},
address={Inc. River Edge, NJ, USA}
}

@article{pangenome, 
author = {The Computational Pan-Genomics Consortium},
title={Computational pan-genomics: status, promises and challenges.},
journal= { Briefings in Bioinformatics},
year= {2016},
pages= {1-18},
}

%21
@article{pantools, 
author = {Sheikhizadeh, S. and Schranz, M.E. and Akdel, M. and de Ridder, D. and Smit, S.},
title={PanTools: representation, storage and exploration of pan-genomic data.},
journal= {Bioinformatics},
year= {2016},
pages= {487-493},
volume={32(17)},
}

%18
@article{panRef, 
author={Nguyen, N. and Hickey, G. and Zerbino, D.R. and Raney, B.J. and Earl, D. and Armstrong, J. and Kent, W.J. and Haussler, D. and Paten, B.},
title={Building a pan-genome reference for a population.},
journal= {Journal of Computational Biology},
year= {2015},
pages= {387-401},
volume={22(5)},
}

@article{Ukkonen95,
	Author = {Ukkonen, Esko},
	Journal = {Algorithmica},
	Number = {3},
	Pages = {249--260},
	Title = {{On-Line Construction of Suffix Trees}},
	Volume = {14},
	Year = {1995}}

@Article{MartensNS09,
  title =	"Complexity of Decision Problems for {XML} Schemas and
		 Chain Regular Expressions",
  author =	"Wim Martens and Frank Neven and Thomas Schwentick",
  journal =	"SIAM Journal of Computing",
  year = 	"2009",
  number =	"4",
  volume =	"39",
  pages =	"1486--1530",
}

@Article{Ukkonen1995,
author="Ukkonen, E.",
title="On-line construction of suffix trees",
journal="Algorithmica",
year="1995",
volume="14",
number="3",
pages="249--260",
issn="1432-0541"
}

@InProceedings{borozdin,
  author =	{Kirill Borozdin and Dmitry Kosolobov and Mikhail Rubinchik and Arseny M. Shur},
  title =	{{Palindromic Length in Linear Time}},
  booktitle =	{28th CPM},
  pages =	{23:1--23:12},
  _series =	{LIPIcs},
  year =	{2017},
  _volume =	{78}
}

@Article{journals/tcs/Williams05,
  title =	"A new algorithm for optimal 2-constraint satisfaction
		 and its implications",
  author =	"Ryan Williams",
  journal =	"Theor. Comput. Sci",
  year = 	"2005",
  number =	"2-3",
  volume =	"348",
  bibdate =	"2017-05-28",
  bibsource =	"DBLP,
		 http://dblp.uni-trier.de/https://doi.org/10.1016/j.tcs.2005.09.023;
		 DBLP,
		 http://dblp.uni-trier.de/db/journals/tcs/tcs348.html#Williams05",
  pages =	"357--365",
}

@article{Lev,
  author    = {Levenshtein, V. I.},
  title     = {Binary Codes Capable of Correcting Deletions, Insertions and Reversals},
  journal   = {Soviet Physics Doklady},
  volume    = {10},
  pages     = {707},
  year      = {1966}
}

@INPROCEEDINGS{Bringmann,
author={K. {Bringmann} and M. {Künnemann}},
booktitle={56th FOCS},
title={Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping},
year={2015},
volume={},
number={},
pages={79-97},
}


@article{missurvey,
 ISSN = {02767783},
 author = {H. J. Smith and T. Dinev and H. Xu},
 journal = {MIS Quarterly},
 number = {4},
 pages = {989--1015},
 title = {Information Privacy Research: An Interdisciplinary Review},
 volume = {35},
 year = {2011}
}

@misc{hipaa,
author={{U.S.} {D}epartment of {H}ealth \& {H}uman {S}ervices},
title={{H}ealth {I}nsurance {P}ortablility and {A}ccountability {A}ct},
howpublished={\url{https://aspe.hhs.gov/report/health-insurance-portability-and-accountability-act-1996}},
year={1996}
}

@misc{gdpr,
author={European Parliament},
title={{G}eneral {D}ata {P}rotection {R}egulation},
howpublished={\url{http://data.consilium.europa.eu/doc/document/ST-9565-2015-INIT/en/pdf}},

}
 

@ARTICLE{hiding,
author={O. {Abul} and F. {Bonchi} and F. {Giannotti}},
journal={IEEE Transactions on Knowledge and Data Engineering},
title={Hiding Sequential and Spatiotemporal Patterns},
year={2010},
volume={22},
number={12},
pages={1709-1723},
doi={10.1109/TKDE.2009.213},
ISSN={2326-3865},
month={Dec},}\textbf{}

@ARTICLE{trajectory,
author={M. {Terrovitis} and G. {Poulis} and N. {Mamoulis} and S. {Skiadopoulos}},
journal={IEEE Transactions on Knowledge and Data Engineering},
title={Local Suppression and Splitting Techniques for Privacy Preserving Publication of Trajectories},
year={2017},
volume={29},
number={7},
pages={1466-1479}
}

@article{locations,
  title={Apriori-based algorithms for km-anonymizing trajectory data},
  author={G. Poulis and S. Skiadopoulos and G. Loukides and A. Gkoulalas-Divanis},
  journal={Transactions on Data Privacy},
  year={2014},
  volume={7},
  pages={165-194}
}

@article{SETH1,
 author = {Impagliazzo, R. and Paturi, R. and Zane, F.},
 title = {Which Problems Have Strongly Exponential Complexity?},
 journal = {Journal of Computer and System Sciences},
 volume = {63},
 number = {4},
 year = {2001},
 issn = {0022-0000},
 pages = {512--530},
 numpages = {19}
} 

@article{SETH2,
 author = {Impagliazzo, R. and Paturi, R.},
 title = {On the Complexity of k-{SAT}},
 journal = {Journal of Computer and Systems Sciences},
 issue_date = {March 2001},
 volume = {62},
 number = {2},
 year = {2001},
 issn = {0022-0000},
 pages = {367--375},
 numpages = {9}
} 

@article{Morrissy2016,
  Author = {Morrissy, A. S. and Garzia, L and {others}},
  Journal = {Nature},
  Month = {01},
  Pages = {351 EP  -},
  Title = {Divergent clonal selection dominates medulloblastoma at recurrence},
  Volume = {529},
  Year = {2016}}
  
  @article{Wang2016,
  Author = {Wang, Jiguang and Cazzato, Emanuela and Ladewig, Erik and Frattini, Veronique and Rosenbloom, Daniel I S and Zairis, Sakellarios and Abate, Francesco and Liu, Zhaoqi and Elliott, Oliver and Shin, Yong-Jae and Lee, Jin-Ku and Lee, In-Hee and Park, Woong-Yang and Eoli, Marica and Blumberg, Andrew J and Lasorella, Anna and Nam, Do-Hyun and Finocchiaro, Gaetano and Iavarone, Antonio and Rabadan, Raul},
  Journal = {Nature Genetics},
  Month = {06},
  Pages = {768 EP  -},
  Title = {Clonal evolution of glioblastoma under therapy},
  Volume = {48},
  Year = {2016}}


@inbook{hajirasouliha14_recon_mutat_histor_multip_sampl,
  author =   {Iman Hajirasouliha and Benjamin J. Raphael},
  booktitle =  {Lecture Notes in Computer Science},
  pages =  {354-367},
  publisher =    {Springer Nature},
  series =     {Lecture Notes in Computer Science},
  title =    {Reconstructing Mutational History in Multiply Sampled Tumors Using Perfect Phylogeny Mixtures},
  year =	   {2014},
}

@article{SCITE_jahn_tree_2016,
	title = {Tree inference for single-cell data},
	volume = {17},
	journal = {Genome Biology},
	author = {Jahn, Katharina and Kuipers, Jack and Beerenwinkel, Niko},
	year = {2016},
	pages = {86},
}

@INPROCEEDINGS{gpps,
author={S. {Ciccolella} and M. S. {Gomez} and M. {Patterson} and G. {Della Vedova} and I. {Hajirasouliha} and P. {Bonizzoni}},
booktitle={8th ICCABS},
title={GPPS: an ILP-based approach for inferring cancer progression with mutation losses from single cell data},
year={2018},
volume={},
number={},
pages={},
}

@Article{Zafar2017,
  author={Zafar, Hamim
      and Tzen, Anthony
      and Navin, Nicholas
      and Chen, Ken
      and Nakhleh, Luay},
  title={SiFit: inferring tumor trees from single-cell sequencing data under finite-sites models},
  journal={Genome Biology},
  year={2017},
  volume={18},
  number={1},
  pages={178},
}

@Article{bscite,
  author={Malikic, Salem
      and Jahn, Katharina
      and Kuipers, Jack
      and Sahinalp, S. Cenk
      and Beerenwinkel, Niko},
  title={Integrative inference of subclonal tumour evolution from single-cell and bulk sequencing data},
  journal={Nature Communications},
  year={2019},
  volume={10},
  number={1},
  pages={2750},}


@Article{sasc,
author = {Ciccolella, Simone and Gomez, Mauricio Soto and Patterson, Murray and Della Vedova, Gianluca and Hajirasouliha, Iman and Bonizzoni, Paola},
title = {Inferring Cancer Progression from Single-cell Sequencing while Allowing Mutation Losses},
year = {2018},
publisher = {Cold Spring Harbor Laboratory},
journal = {Bioinformatics}}

@article{siamcomp/AhoSSU81,
  author    = {Alfred V. Aho and
               Yehoshua Sagiv and
               Thomas G. Szymanski and
               Jeffrey D. Ullman},
  title     = {Inferring a Tree from Lowest Common Ancestors with an Application
               to the Optimization of Relational Expressions.},
  journal   = Sicomp,
  volume    = {10},
  number    = {3},
  year      = {1981},
  pages     = {405-421},
}

@article{Kuipers13102017,
  author = {Kuipers, Jack and Jahn, Katharina and Raphael, Benjamin J. and Beerenwinkel, Niko},
  title = {Single-cell sequencing data reveal widespread recurrence and loss of mutational hits in the life histories of tumors},
  year = {2017},
  journal = {Genome Research}
}

@Article{Brown2017,
  author={Brown, David
      and Smeets, Dominiek
      and Székely, Borbála
      and Larsimont, Denis
      and Szász, A. Marcell
      and Adnet, Pierre-Yves
      and Rothé, Françoise
      and Rouas, Ghizlane
      and Nagy, Zsófia I.
      and Faragó, Zsófia
      and Tokés, Anna-Mária
      and Dank, Magdolna
      and Szentmártoni, Győngyvér
      and Udvarhelyi, Nóra
      and Zoppoli, Gabriele
      and Pusztai, Lajos
      and Piccart, Martine
      and Kulka, Janina
      and Lambrechts, Diether
      and Sotiriou, Christos
      and Desmedt, Christine},
  title={Phylogenetic analysis of metastatic progression in breast cancer using somatic mutations and copy number aberrations},
  journal={Nature Communications},
  year={2017},
  publisher={The Author(s) SN  -},
  volume={8},
  pages={14944 EP  -},
  }
  
  @article{10.1093/bioinformatics/btz312,
author = {Aguse, Nuraini and Qi, Yuanyuan and El-Kebir, Mohammed},
title = "{Summarizing the solution space in tumor phylogeny inference by multiple consensus trees}",
journal = {Bioinformatics},
volume = {35},
number = {14},
pages = {i408-i416},
year = {2019},
}

@Article{Karpov2019,
  author={Karpov, Nikolai
      and Malikic, Salem
      and Rahman, Md Khaledur
      and Sahinalp, S. Cenk},
  title={A multi-labeled tree dissimilarity measure for comparing "clonal trees" of tumor progression},
  journal={Algorithms for Molecular Biology},
  year={2019},
  volume={14},
  number={1},
  pages={17},
}

@article{janssonMorePracticalAlgorithm2016,
	title = {A {More} {Practical} {Algorithm} for the {Rooted} {Triplet} {Distance}},
	journal = {Journal of Computational Biology},
	author = {Jansson, Jesper and Rajaby, Ramesh},
	year = {2016},
}
@article{gerlinger_real,
  title={Genomic architecture and evolution of clear cell renal cell carcinomas defined by multiregion sequencing},
  author={Gerlinger, Marco and Horswell, Stuart and Larkin, James and Rowan, Andrew J and Salm, Max P and Varela, Ignacio and Fisher, Rosalie and McGranahan, Nicholas and Matthews, Nicholas and Santos, Claudio R and others},
  journal={Nature genetics},
  volume={46},
  number={3},
  pages={225},
  year={2014},
  publisher={Nature Publishing Group}
}

@article{eirew_real,
  title={Dynamics of genomic clones in breast cancer patient xenografts at single-cell resolution},
  author={Eirew, Peter and Steif, Adi and Khattra, Jaswinder and Ha, Gavin and Yap, Damian and Farahani, Hossein and Gelmon, Karen and Chia, Stephen and Mar, Colin and Wan, Adrian and others},
  journal={Nature},
  volume={518},
  number={7539},
  pages={422--426},
  year={2015},
  publisher={Nature Publishing Group}
}


@article{mipup,
  title={MIPUP: minimum perfect unmixed phylogenies for multi-sampled tumors via branchings and ILP},
  author={Husi{\'c}, Edin and Li, Xinyue and Hujdurovi{\'c}, Ademir and Mehine, Miika and Rizzi, Romeo and M{\"a}kinen, Veli and Milani{\v{c}}, Martin and Tomescu, Alexandru I},
  journal={Bioinformatics},
  volume={35},
  number={5},
  pages={769--777},
  year={2019},
  publisher={Oxford University Press}
}

@article{lichee,
  title={Fast and scalable inference of multi-sample cancer lineages},
  author={Popic, Victoria and Salari, Raheleh and Hajirasouliha, Iman and Kashef-Haghighi, Dorna and West, Robert B and Batzoglou, Serafim},
  journal={Genome biology},
  volume={16},
  number={1},
  pages={91},
  year={2015},
  publisher={Springer}
}

@article{IDPP,
  title={Incomplete Directed Perfect Phylogeny in Linear Time},
  author={Bernardini, Giulia and Bonizzoni, Paola and Gawrychowski, Pawel},
  journal={arXiv:2010.05644},
  year={2020}
}

@article{AlstrupSS97,
  author    = {Stephen Alstrup and
               Jens P. Secher and
               Maz Spork},
  title     = {Optimal On-Line Decremental Connectivity in Trees},
  journal   = {Inf. Process. Lett.},
  volume    = {64},
  number    = {4},
  pages     = {161--164},
  year      = {1997}
}

@article{EvenS81,
  author    = {Shimon Even and
               Yossi Shiloach},
  title     = {An On-Line Edge-Deletion Problem},
  journal   = {J. {ACM}},
  volume    = {28},
  number    = {1},
  pages     = {1--4},
  year      = {1981}
}

@article{pe2004incomplete,
  title={Incomplete directed perfect phylogeny},
  author={Pe'er, Itsik and Pupko, Tal and Shamir, Ron and Sharan, Roded},
  journal={SIAM Journal on Computing},
  volume={33},
  number={3},
  pages={590--607},
  year={2004},
  publisher={SIAM}
}

@article{gusfield1991efficient,
  title={Efficient algorithms for inferring evolutionary trees},
  author={Gusfield, Dan},
  journal={Networks},
  volume={21},
  number={1},
  pages={19--28},
  year={1991},
  publisher={Wiley Online Library}
}

@article{bodlaender2000hardness,
  title={The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs},
  author={Bodlaender, Hans L and Fellows, Michael R and Hallett, Michael T and Wareham, H Todd and Warnow, Tandy J},
  journal={Theoretical Computer Science},
  volume={244},
  number={1-2},
  pages={167--188},
  year={2000},
  publisher={Elsevier}
}

@article{camin1965method,
  title={A method for deducing branching sequences in phylogeny},
  author={Camin, Joseph H and Sokal, Robert R},
  journal={Evolution},
  pages={311--326},
  year={1965},
  publisher={JSTOR}
}

@article{meacham1985compatibility,
  title={Compatibility methods in systematics},
  author={Meacham, Christopher A and Estabrook, George F},
  journal={Annual Review of Ecology and Systematics},
  volume={16},
  number={1},
  pages={431--446},
  year={1985},
  publisher={Annual Reviews 4139 El Camino Way, PO Box 10139, Palo Alto, CA 94303-0139, USA}
}

@article{eppstein1997sparsification,
  title={Sparsification—a technique for speeding up dynamic graph algorithms},
  author={Eppstein, David and Galil, Zvi and Italiano, Giuseppe F and Nissenzweig, Amnon},
  journal={J. {ACM}},
  volume={44},
  number={5},
  pages={669--696},
  year={1997},
  publisher={ACM New York, NY, USA}
}

@article{holm2001poly,
  title={Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity},
  author={Holm, Jacob and De Lichtenberg, Kristian and Thorup, Mikkel},
  journal={J. {ACM}},
  volume={48},
  number={4},
  pages={723--760},
  year={2001},
  publisher={ACM New York, NY, USA}
}

@article{fernandez2019tree,
  title={Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: An experimental study},
  author={Fern{\'a}ndez-Baca, David and Liu, Lei},
  journal={Algorithms},
  volume={12},
  number={3},
  pages={53},
  year={2019},
  publisher={Multidisciplinary Digital Publishing Institute}
}

@article{henzinger1999randomized,
  title={Randomized fully dynamic graph algorithms with polylogarithmic time per operation},
  author={Henzinger, Monika R and King, Valerie},
  journal={J. {ACM}},
  volume={46},
  number={4},
  pages={502--516},
  year={1999},
  publisher={ACM New York, NY, USA}
}

@inproceedings{kapron2013dynamic,
  title={Dynamic graph connectivity in polylogarithmic worst case time},
  author={Kapron, Bruce M and King, Valerie and Mountjoy, Ben},
  booktitle={24th SODA},
  pages={1131--1142},
  year={2013},
  organization={SIAM}
}

@article{thorup1999decremental,
  title={Decremental dynamic connectivity},
  author={Thorup, Mikkel},
  journal={Journal of Algorithms},
  volume={33},
  number={2},
  pages={229--243},
  year={1999},
  publisher={Elsevier}
}

@inproceedings{huang2017fully,
  title={Fully dynamic connectivity in {$O(\log n(\log\log n)^2)$} amortized expected time},
  author={Huang, Shang-En and Huang, Dawei and Kopelowitz, Tsvi and Pettie, Seth},
  booktitle={28th SODA},
  pages={510--520},
  year={2017},
  _organization={SIAM}
}

@article{gibb2015dynamic,
  title={Dynamic graph connectivity with improved worst case update time and sublinear space},
  author={Gibb, David and Kapron, Bruce and King, Valerie and Thorn, Nolan},
  journal={arXiv:1509.06464},
  year={2015}
}

@article{henzinger1999constructing,
  title={Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology},
  author={Henzinger, Monika Rauch and King, Valerie and Warnow, Tandy},
  journal={Algorithmica},
  volume={24},
  number={1},
  pages={1--13},
  year={1999},
  publisher={Springer}
}

@article{kimmel2005incomplete,
  title={The incomplete perfect phylogeny haplotype problem},
  author={Kimmel, Gad and Shamir, Ron},
  journal={Journal of Bioinformatics and Computational Biology},
  volume={3},
  number={02},
  pages={359--384},
  year={2005},
  publisher={World Scientific}
}

@article{iyer2001experimental,
  title={An experimental study of polylogarithmic, fully dynamic, connectivity algorithms},
  author={Iyer, Raj and Karger, David and Rahul, Hariharan and Thorup, Mikkel},
  journal={Journal of Experimental Algorithmics (JEA)},
  volume={6},
  pages={4--es},
  year={2001},
  publisher={ACM New York, NY, USA}
}

@article{bonizzoni2012binary,
  title={The binary perfect phylogeny with persistent characters},
  author={Bonizzoni, Paola and Braghin, Chiara and Dondi, Riccardo and Trucco, Gabriella},
  journal={Theoretical Computer Science},
  volume={454},
  pages={51--63},
  year={2012},
  publisher={Elsevier}
}

@inproceedings{gusfield2015persistent,
  title={Persistent phylogeny: a galled-tree and integer linear programming approach},
  author={Gusfield, Dan},
  booktitle={6th ACM-BCB},
  pages={443--451},
  year={2015}
}


@article{satas2020scarlet,
  title={SCARLET: Single-Cell Tumor Phylogeny Inference with Copy-Number Constrained Mutation Losses},
  author={Satas, Gryte and Zaccaria, Simone and Mon, Geoffrey and Raphael, Benjamin J},
  journal={Cell Systems},
  volume={10},
  number={4},
  pages={323--332},
  year={2020},
  publisher={Elsevier}
}

@article{bashir2005orthologous,
  title={Orthologous repeats and mammalian phylogenetic inference},
  author={Bashir, Ali and Ye, Chun and Price, Alkes L and Bafna, Vineet},
  journal={Genome Research},
  volume={15},
  number={7},
  pages={998--1006},
  year={2005},
  publisher={Cold Spring Harbor Lab}
}

@article{nikaido1999phylogenetic,
  title={Phylogenetic relationships among cetartiodactyls based on insertions of short and long interpersed elements: hippopotamuses are the closest extant relatives of whales},
  author={Nikaido, Masato and Rooney, Alejandro P and Okada, Norihiro},
  journal={Proceedings of the National Academy of Sciences},
  volume={96},
  number={18},
  pages={10261--10266},
  year={1999},
  publisher={National Acad Sciences}
}

@ARTICLE{6819844,
  author={B. {Kirkpatrick} and K. {Stevens}},
  journal={IEEE/ACM Transactions on Computational Biology and Bioinformatics}, 
  title={Perfect Phylogeny Problems with Missing Values}, 
  year={2014},
  volume={11},
  number={5},
  pages={928-941},}
  
  @ARTICLE{satya2008,
  author={R. V. {Satya} and A. {Mukherjee}},
  journal={IEEE/ACM Transactions on Computational Biology and Bioinformatics}, 
  title={The Undirected Incomplete Perfect Phylogeny Problem}, 
  year={2008},
  volume={5},
  number={4},
  pages={618-629},}
  
  @inproceedings{stevens2010reducing,
  title={Reducing multi-state to binary perfect phylogeny with applications to missing, removable, inserted, and deleted data},
  author={Stevens, Kristian and Gusfield, Dan},
  booktitle={10th WABI},
  pages={274--287},
  year={2010},
  organization={Springer}
}


@article{el2018sphyr,
  title={SPhyR: tumor phylogeny estimation from single-cell sequencing data under loss and error},
  author={El-Kebir, Mohammed},
  journal={Bioinformatics},
  volume={34},
  number={17},
  pages={i671--i679},
  year={2018},
  publisher={Oxford University Press}
}

@article{kersey2016ensembl,
  title={Ensembl Genomes 2016: more genomes, more complexity},
  author={Kersey, Paul Julian and Allen, James E and Armean, Irina and Boddu, Sanjay and Bolt, Bruce J and Carvalho-Silva, Denise and Christensen, Mikkel and Davis, Paul and Falin, Lee J and Grabmueller, Christoph and others},
  journal={Nucleic acids research},
  volume={44},
  number={D1},
  pages={D574--D580},
  year={2016},
  publisher={Oxford University Press}
}

@article{nguyen2015building,
  title={Building a pan-genome reference for a population},
  author={Nguyen, Ngan and Hickey, Glenn and Zerbino, Daniel R and Raney, Brian and Earl, Dent and Armstrong, Joel and Kent, W James and Haussler, David and Paten, Benedict},
  journal={Journal of Computational Biology},
  volume={22},
  number={5},
  pages={387--401},
  year={2015},
  publisher={Mary Ann Liebert, Inc. 140 Huguenot Street, 3rd Floor New Rochelle, NY 10801 USA}
}

@article{sheikhizadeh2016pantools,
  title={PanTools: representation, storage and exploration of pan-genomic data},
  author={Sheikhizadeh, Siavash and Schranz, M Eric and Akdel, Mehmet and de Ridder, Dick and Smit, Sandra},
  journal={Bioinformatics},
  volume={32},
  number={17},
  pages={i487--i493},
  year={2016},
  publisher={Oxford University Press}
}

@article{alzamel2020comparing,
  title={Comparing Degenerate Strings},
  author={Alzamel, Mai and Ayad, Lorraine AK and Bernardini, Giulia and Grossi, Roberto and Iliopoulos, Costas S and Pisanti, Nadia and Pissis, Solon P and Rosone, Giovanna},
  journal={Fundamenta Informaticae},
  volume={175},
  number={1-4},
  pages={41--58},
  year={2020},
  publisher={IOS Press}
}

@article{ACint,
  author    = {Shiri Dori and
               Gad M. Landau},
  title     = {Construction of Aho Corasick automaton in linear time for integer
               alphabets},
  journal   = {Inf. Process. Lett.},
  volume    = {98},
  number    = {2},
  pages     = {66--72},
  year      = {2006},
  _url       = {https://doi.org/10.1016/j.ipl.2005.11.019},
  _doi       = {10.1016/j.ipl.2005.11.019},
  timestamp = {Fri, 26 May 2017 22:54:41 +0200},
  biburl    = {https://dblp.org/rec/journals/ipl/DoriL06.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{injector,
  author    = {Tiancheng Li and
               Ninghui Li},
  editor    = {Gustavo Alonso and
               Jos{\'{e}} A. Blakeley and
               Arbee L. P. Chen},
  title     = {Injector: Mining Background Knowledge for Data Anonymization},
  booktitle = {24th
               {ICDE}},
  pages     = {446--455},
  _publisher = {{IEEE} Computer Society},
  year      = {2008},
  _url       = {https://doi.org/10.1109/ICDE.2008.4497453},
  _doi       = {10.1109/ICDE.2008.4497453},
  _timestamp = {Wed, 16 Oct 2019 14:14:56 +0200},
  _biburl    = {https://dblp.org/rec/conf/icde/LiL08.bib},
  _bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{atzori,
  author    = {Maurizio Atzori and
               Francesco Bonchi and
               Fosca Giannotti and
               Dino Pedreschi},
  title     = {Anonymity preserving pattern discovery},
  journal   = {{VLDB} J.},
  volume    = {17},
  number    = {4},
  pages     = {703--727},
  year      = {2008},
  _url       = {https://doi.org/10.1007/s00778-006-0034-x},
  _doi       = {10.1007/s00778-006-0034-x},
  _timestamp = {Sun, 28 May 2017 13:19:15 +0200},
  _biburl    = {https://dblp.org/rec/journals/vldb/AtzoriBGP08.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}


@article{AC,
author = {Aho, Alfred V. and Corasick, Margaret J.},
title = {Efficient String Matching: An Aid to Bibliographic Search},
year = {1975},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {18},
number = {6},
_issn = {0001-0782},
_url = {https://doi.org/10.1145/360825.360855},
_doi = {10.1145/360825.360855},
_abstract = {This paper describes a simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. The algorithm consists of constructing a finite state pattern matching machine from the keywords and then using the pattern matching machine to process the text string in a single pass. Construction of the pattern matching machine takes time proportional to the sum of the lengths of the keywords. The number of state transitions made by the pattern matching machine in processing the text string is independent of the number of keywords. The algorithm has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.},
journal = {Commun. ACM},
pages = {333-340},
numpages = {8},
_keywords = {computational complexity, information retrieval, finite state machines, keywords and phrases, string pattern matching, bibliographic search, text-editing}
}

  
@inproceedings{DBLP:conf/pods/SamaratiS98,
  author    = {Pierangela Samarati and
               Latanya Sweeney},
  _editor    = {Alberto O. Mendelzon and
               Jan Paredaens},
  title     = {Generalizing Data to Provide Anonymity when Disclosing Information
               (Abstract)},
  booktitle = {17th {ACM} {SIGACT-SIGMOD-SIGART}},
  pages     = {188},
  _publisher = {{ACM} Press},
  year      = {1998},
  _url       = {https://doi.org/10.1145/275487.275508},
  _doi       = {10.1145/275487.275508},
  _timestamp = {Tue, 06 Nov 2018 16:58:02 +0100},
  _biburl    = {https://dblp.org/rec/conf/pods/SamaratiS98.bib},
  _bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/tcs/CarpiL01,
  author    = {Arturo Carpi and
               Aldo de Luca},
  title     = {Words and special factors},
  journal   = {Theoretical Computer Science},
  volume    = {259},
  number    = {1-2},
  pages     = {145--182},
  year      = {2001},
  _url       = {https://doi.org/10.1016/S0304-3975(99)00334-5},
  _doi       = {10.1016/S0304-3975(99)00334-5},
}
@article{heatherly,
    author = {Heatherly, Raymond D. AND Loukides, Grigorios AND Denny, Joshua C. AND Haines, Jonathan L. AND Roden, Dan M. AND Malin, Bradley A.},
    journal = {PLOS ONE},
    publisher = {Public Library of Science},
    title = {Enabling Genomic-Phenomic Association Discovery without Sacrificing Anonymity},
    year = {2013},
    month = {02},
    volume = {8},
    _url = {https://doi.org/10.1371/journal.pone.0053875},
    pages = {1-13},
}

@article{LU,
title={A supernodal approach to sparse partial pivoting}, 
author={Demmel, James Weldon and Eisenstat, Stanley C. and Gilbert, John R.  and Li, Xiaoye S. and Liu, Joseph W. H. }, 
journal={{SIAM} Journal on Matrix Analysis and Applications},
volume={20},
number={3},
pages={720–755},
year={1999},
}
  
  @article{km1,
 author = {Terrovitis, Manolis and Mamoulis, Nikos and Kalnis, Panos},
 title = {Local and Global Recoding Methods for Anonymizing Set-valued Data},
 journal = {The VLDB Journal},
 issue_date = {February  2011},
 volume = {20},
 number = {1},

 year = {2011},
 issn = {1066-8888},
 pages = {83--106},
 numpages = {24},
 
} 
@article{km2,
  author    = {Giorgos Poulis and
               Spiros Skiadopoulos and
               Grigorios Loukides and
               Aris Gkoulalas{-}Divanis},
  title     = {Apriori-based algorithms for k\({}^{\mbox{m}}\)-anonymizing trajectory
               data},
  journal   = {Transactions on Data Privacy},
  volume    = {7},
  number    = {2},
  pages     = {165--194},
  year      = {2014},
  }
@INPROCEEDINGS{terr,
author={Manolis Terrovitis and Nikos Mamoulis},
booktitle={9th MDM},
title={Privacy Preservation in the Publication of Trajectories},
year={2008},
volume={},
number={},
pages={65-72}, 
}

@article {pnas,
	author = {Loukides, Grigorios and Gkoulalas-Divanis, Aris and Malin, Bradley},
	title = {Anonymization of electronic medical records for validating genome-wide association studies},
	journal={Proceedings of the National Academy of Sciences {USA}},
	volume = {107},
	number = {17},
	pages = {7898--7903},
	year = {2010},
	}
	
 @article{lkc,
 author = {Mohammed, Noman and Fung, Benjamin C. M. and Hung, Patrick C. K. and Lee, Cheuk-Kwong},
 title = {Centralized and Distributed Anonymization for High-Dimensional Healthcare Data},
 journal = {ACM Transactions on Knowledge Discovery from Data},
 issue_date = {2010},
 year = {2010},
 issn = {1556-4681},
 pages = {18:1--18:33},
 articleno = {18},
 numpages = {33},
 }

@article{Grossi:2017:AOE:3040971.3012939,
 author = {Grossi, Roberto and Iacono, John and Navarro, Gonzalo and Raman, Rajeev and Satti, S. Rao},
 title = {Asymptotically Optimal Encodings of Range Data Structures for Selection and Top-k Queries},
 journal = {ACM Transactions on Algorithms},
 volume = {13},
 number = {2},
 year = {2017},
 issn = {1549-6325},
 pages = {28:1--28:31},
 articleno = {28},
 numpages = {31},
 _url = {http://doi.acm.org/10.1145/3012939},
 _doi = {10.1145/3012939},
 acmid = {3012939},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Succinct data structures, encoding data structures, range minimum queries, range search data structures},
} 

@inproceedings{DBLP:conf/walcom/Raman15,
  author    = {Rajeev Raman},
  title     = {Encoding Data Structures},
  booktitle = {9th WALCOM},
  pages     = {1--7},
  year      = {2015},
}
@misc{eigen,
author={Software}, 
title={Eigen library},
howpublished={\url{http://eigen.tuxfamily.org}},
year={2020}
}

@article{xiaotods,
 author = {Xiao, Xiaokui and Tao, Yufei and Koudas, Nick},
 title = {Transparent Anonymization: Thwarting Adversaries Who Know the Algorithm},
 journal = {ACM Transactions on Database Systems},
 volume = {35},
 number = {2},
 year = {2010},
 pages = {8:1--8:48},
 }

 @article{DBLP:journals/ejc/CrochemoreIIKRW13,
  author    = {Maxime Crochemore and
               Lucian Ilie and
               Costas S. Iliopoulos and
               Marcin Kubica and
               Wojciech Rytter and
               Tomasz Walen},
  title     = {Computing the Longest Previous Factor},
  journal   = {Eur. J. Comb.},
  volume    = {34},
  number    = {1},
  pages     = {15--26},
  year      = {2013},
  _url       = {https://doi.org/10.1016/j.ejc.2012.07.011},
  _doi       = {10.1016/j.ejc.2012.07.011},
  timestamp = {Sun, 02 Jun 2019 21:04:22 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/ejc/CrochemoreIIKRW13},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@incollection{nabar,
author="Nabar, Shubha U.
and Kenthapadi, Krishnaram
and Mishra, Nina
and Motwani, Rajeev",
_editor="Aggarwal, Charu C.
and Yu, Philip S.",
title="A Survey of Query Auditing Techniques for Data Privacy",
booktitle="Privacy-Preserving Data Mining: Models and Algorithms",
year="2008",
publisher="Springer US",
pages="415--431",
_isbn="978-0-387-70992-5",
_doi="10.1007/978-0-387-70992-5_17",
_url="https://doi.org/10.1007/978-0-387-70992-5_17"
}
@article{kacs,
    author = {Leimeister, Chris-Andre and Morgenstern, Burkhard},
    title = "{ {K}macs: the $k$-mismatch average common substring approach to alignment-free sequence comparison}",
    journal = {Bioinformatics},
    volume = {30},
    number = {14},
    pages = {2000-2008},
    year = {2014},
    }
    
@article{nj,
    author = {Naruya Saitou and Masatoshi Nei},
    title = "{The neighbor-joining method: a new method for reconstructing phylogenetic trees.}",
    journal = {Molecular Biology and Evolution},
    volume = {4},
    number = {4},
    pages = {406-425},
    year = {1987},
    month = {07},
    }
    
@book{zaki2014data,
  title={Data mining and analysis: fundamental concepts and algorithms},
  author={Mohammed J. Zaki and Wagner Meira Jr and Wagner Meira},
  year={2014},
  publisher={Cambridge University Press}
}

@article{takeaki,
author="Arimura, Hiroki and Uno, Takeaki",
title="An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence",
journal="Journal of Combinatorial Optimization",
year="2007",
volume="13",
number="3",
pages="243--262",
}

@article{alfred,
  author    = {Sharma V. Thankachan and
               Sriram P. Chockalingam and
               Yongchao Liu and
               Ambujam Krishnan and
               Srinivas Aluru},
  title     = {A greedy alignment-free distance estimator for phylogenetic inference},
  journal   = {{BMC} Bioinformatics},
  volume    = {18},
  number    = {8},
  pages     = {238:1--238:8},
  year      = {2017},
  }
  
@article{dendroscope,
author={Huson, D. H., Richter, D. C., Rausch, C., Dezulian, T., Franz, M., & Rupp, R},
year={2007},
title={Dendroscope: An interactive viewer for large phylogenetic trees},
journal={{BMC} Bioinformatics},
volume={8}, 
number={460},
}  
  
@inproceedings{karp,
 author = {Karp, Richard M. and Miller, Raymond E. and Rosenberg, Arnold L.},
 title = {Rapid Identification of Repeated Patterns in Strings, Trees and Arrays},
 booktitle = {4th STOC},
 series = {STOC '72},
 year = {1972},
 pages = {125--136},
 numpages = {12},
 }
 
@BOOK{bertino,
author={Elisa Bertino and Gabriel Ghinita and Ashish Kamra},
booktitle={Access Control for Databases: Concepts and Systems},
title={Access Control for Databases: Concepts and Systems},
year={2011},
volume={},
number={},
pages={},
keywords={Databases;Information Sciences;Digital Security},
doi={},
ISSN={},
publisher={Now Foundations and Trends}, 
}

@article{acartitb,
  author    = {Acar Tamersoy and
               Grigorios Loukides and
               Mehmet Ercan Nergiz and
               Y{\"{u}}cel Saygin and
               Bradley Malin},
  title     = {Anonymization of Longitudinal Electronic Medical Records},
  journal   = {{IEEE} Transactions on  Information Technology in Biomedicine},
  volume    = {16},
  number    = {3},
  pages     = {413--423},
  year      = {2012},
 }

@book{irbook,
 author = {Manning, Christopher D. and Raghavan, Prabhakar and Sch\"{u}tze, Hinrich},
 title = {Introduction to Information Retrieval},
 year = {2008},
 isbn = {0521865719, 9780521865715},
 publisher = {Cambridge University Press},
IGNOREaddress = {New York, NY, USA},
} 

@article{fptree,
 author = {Han, Jiawei and Pei, Jian and Yin, Yiwen},
 title = {Mining Frequent Patterns Without Candidate Generation},
 journal = {SIGMOD Record},
 issue_date = {June 2000},
 volume = {29},
 number = {2},
 month = may,
 year = {2000},
 issn = {0163-5808},
 pages = {1--12},
 numpages = {12},
 }
@article{knn,
 author = {Lu, Wei and Shen, Yanyan and Chen, Su and Ooi, Beng Chin},
 title = {Efficient Processing of K Nearest Neighbor Joins Using MapReduce},
 journal = {Proc. VLDB Endow.},
 issue_date = {June 2012},
 volume = {5},
 number = {10},
 month = jun,
 year = {2012},
 issn = {2150-8097},
 pages = {1016--1027},
 numpages = {12},
 }
@inproceedings{edbt16,
  author    = {Jing Wang and
               Nikos Ntarmos and
               Peter Triantafillou},
  title     = {Indexing Query Graphs to Speedup Graph Query Processing},
  booktitle = {19th EDBT},
  pages     = {41--52},
  year      = {2016},
  }
@inproceedings{rtree,
 author = {Guttman, Antonin},
 title = {R-trees: A Dynamic Index Structure for Spatial Searching},
 booktitle = {SIGMOD},
 year = {1984},
 pages = {47--57},
 }
 
@inproceedings{cpap1,
 author = {Demertzis, Ioannis and Papamanthou, Charalampos},
 title = {Fast Searchable Encryption With Tunable Locality},
 booktitle = {SIGMOD},
 year = {2017},
 pages = {1053--1067}}
 


 @article{BENTLEY2006545,
title = "Whole-genome re-sequencing",
journal = "Current Opinion in Genetics \& Development",
volume = "16",
number = "6",
pages = "545--552",
year = "2006",
issn = "0959-437X",
_doi = "https://doi.org/10.1016/j.gde.2006.10.009",
_url = "http://www.sciencedirect.com/science/article/pii/S0959437X06002085",
author = "David R. Bentley",
}

 
@InProceedings{krkkinen_et_al:LIPIcs:2017:7498,
  author =	{Juha K{\"a}rkk{\"a}inen and Marcin Piatkowski and Simon J. Puglisi},
  title =	{{String Inference from Longest-Common-Prefix Array}},
  booktitle =	{44th ICALP},
  pages =	{62:1--62:14},
  year =	{2017},
} 

@inproceedings{DBLP:conf/latin/Charalampopoulos18,
  author    = {Panagiotis Charalampopoulos and
               Costas S. Iliopoulos and
               Chang Liu and
               Solon P. Pissis},
  title     = {Property Suffix Array with Applications},
  booktitle = {13th LATIN},
  pages     = {290--302},
  year      = {2018},
  IGNOREcrossref  = {DBLP:conf/latin/2018},
  IGNOREurl       = {https://doi.org/10.1007/978-3-319-77404-6\_22},
  IGNOREdoi       = {10.1007/978-3-319-77404-6\_22},
  IGNOREtimestamp = {Tue, 14 May 2019 10:00:53 +0200},
  IGNOREbiburl    = {https://dblp.org/rec/bib/conf/latin/Charalampopoulos18},
  IGNOREbibsource = {dblp computer science bibliography, https://dblp.org}
}


@proceedings{DBLP:conf/focs/1997,
  title     = {38th Annual Symposium on Foundations of Computer Science, {FOCS} '97,
               Miami Beach, Florida, USA, October 19-22, 1997},
  publisher = {{IEEE} Computer Society},
  year      = {1997},
  _url       = {http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5208},
  isbn      = {0-8186-8197-7},
  timestamp = {Mon, 15 Dec 2014 18:48:44 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/focs/1997},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}



@proceedings{DBLP:conf/latin/2018,
  editor    = {Michael A. Bender and
               Martin Farach{-}Colton and
               Miguel A. Mosteiro},
  title     = {{LATIN} 2018: Theoretical Informatics--13th Latin American Symposium,
               Buenos Aires, Argentina, April 16-19, 2018, Proceedings},
  series    = {Lecture Notes in Computer Science},
  volume    = {10807},
  publisher = {Springer},
  year      = {2018},
  _url       = {https://doi.org/10.1007/978-3-319-77404-6},
  _doi       = {10.1007/978-3-319-77404-6},
  isbn      = {978-3-319-77403-9},
  timestamp = {Tue, 14 May 2019 10:00:53 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/latin/2018},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}


 
@ARTICLE{GausGil,
author={K. {He} and S. X. -. {Tan} and H. {Wang} and G. {Shi}},
journal={IEEE Transactions on Very Large Scale Integration (VLSI) Systems},
title={GPU-Accelerated Parallel Sparse LU Factorization Method for Fast Circuit Analysis},
year={2016},
volume={24},
number={3},
pages={1140-1150}, 
}

@article{bacchus,
 author = {Bacchus, Fahiem and Grove, Adam J. and Halpern, Joseph Y. and Koller, Daphne},
 title = {From Statistical Knowledge Bases to Degrees of Belief},
 journal = {Artificial Intelligence},
 issue_date = {Nov. 1996},
 volume = {87},
 number = {1-2},
 year = {1996},
 issn = {0004-3702},
 pages = {75--143},
 }
 
@article{journals/jcb/UlitskyBTC06,
  added-at = {2018-11-30T00:00:00.000+0100},
  author = {Ulitsky, Igor and Burstein, David and Tuller, Tamir and Chor, Benny},
  biburl = {https://www.bibsonomy.org/bibtex/27ab8ecd5101c50c3d5829715b480b13f/dblp},
  ee = {https://www.wikidata.org/entity/Q34510984},
  interhash = {470b0d6f978d6709741c99a9d5211e82},
  intrahash = {7ab8ecd5101c50c3d5829715b480b13f},
  journal = {Journal of Computational Biology},
  keywords = {dblp},
  number = 2,
  pages = {336-350},
  timestamp = {2018-12-01T12:02:44.000+0100},
  title = {The Average Common Substring Approach to Phylogenomic Reconstruction.},
  _url = {http://dblp.uni-trier.de/db/journals/jcb/jcb13.html#UlitskyBTC06},
  volume = 13,
  year = 2006
}

@article{gilbert,
 author = {Gilbert, John R. and Peierls, Tim},
 title = {Sparse Partial Pivoting in Time Proportional to Arithmetic Operations},
 journal = {SIAM Journal on Scientific Computing},
 issue_date = {1988},
 volume = {9},
 number = {5},
 year = {1988},
 pages = {862--874},
 }
 
@proceedings{DBLP:conf/focs/FOCS14,
  title     = {14th Annual Symposium on Switching and Automata Theory, Iowa City,
               Iowa, USA, October 15-17, 1973},
  publisher = {{IEEE} Computer Society},
  year      = {1973},
  _url       = {http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4569717},
  timestamp = {Mon, 15 Dec 2014 18:48:44 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/focs/FOCS14},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

 
 @article{DBLP:journals/algorithmica/Ukkonen95,
  author    = {Esko Ukkonen},
  title     = {On-Line Construction of Suffix Trees},
  journal   = {Algorithmica},
  volume    = {14},
  number    = {3},
  pages     = {249--260},
  year      = {1995},
  _url       = {https://doi.org/10.1007/BF01206331},
  _doi       = {10.1007/BF01206331},
  timestamp = {Wed, 14 Nov 2018 10:49:04 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/algorithmica/Ukkonen95},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}
 
  @inproceedings{difpriv2,
 author = {Rui Chen and Gergely Acs and Claude Castelluccia},
 title = {Differentially Private Sequential Data Publication via Variable-length N-grams},
 booktitle = {19th CCS},
 year = {2012},
 pages = {638--649},
 }
 
 
 @INPROCEEDINGS{enc1,
author={Bruhadeshwar Bezawada and Alex X. Liu and Bargav Jayaraman and Ann L. Wang and Rui Li},

booktitle={35th ICDCS},
title={Privacy Preserving String Matching for Cloud Computing},
year={2015},
volume={},
number={},
pages={609-618}, 
}
@INPROCEEDINGS{enc2,
author={Jin Li and Qian Wang and Cong Wang and Ning Cao and Kui Ren and Wenjing Lou},
booktitle={29th INFOCOM},
title={Fuzzy Keyword Search over Encrypted Data in Cloud Computing},
year={2010},
volume={},
number={},
pages={1-5}, 
}

@article{DBLP:journals/siamcomp/FischerH11,
  author    = {Johannes Fischer and
               Volker Heun},
  title     = {Space-Efficient Preprocessing Schemes for Range Minimum Queries on
               Static Arrays},
  journal   = {{SIAM} Journal on Computing},
  volume    = {40},
  number    = {2},
  pages     = {465--492},
  year      = {2011},
  _url       = {https://doi.org/10.1137/090779759},
  _doi       = {10.1137/090779759},
  timestamp = {Wed, 14 Nov 2018 10:45:06 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/siamcomp/FischerH11},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/tcs/HoffmannINR18,
  author    = {Michael Hoffmann and
               John Iacono and
               Patrick K. Nicholson and
               Rajeev Raman},
  title     = {Encoding nearest larger values},
  journal   = {Theoretical Computer Science},
  volume    = {710},
  pages     = {97--115},
  year      = {2018},
}


 @ARTICLE{enc3,
author={Hong Qin and Hao Wang and Xiaochao Wei and Likun Xue and Lei Wu},
journal={IEEE Access},
title={Privacy-Preserving Wildcards Pattern Matching Protocol for IoT Applications},
year={2019},
volume={7},
number={},
pages={36094-36102}, 
}
 @ARTICLE{difpriv3,
author={Shengzhi Xu and Xiang Cheng and Sen Su and Ke Xiao and Li Xiong},
journal={IEEE Transactions on Knowledge and Data Engineering},
title={Differentially Private Frequent Sequence Mining},
year={2016},
volume={28},
number={11},
pages={2910-2926}, 
}
@inproceedings{difpriv1,
 author = {Chen, Rui and Fung, Benjamin C.M. and Desai, Bipin C. and Sossou, N{\'e}riah M.},
 title = {Differentially Private Transit Data Publication: A Case Study on the Montreal Transportation System},
 booktitle = {18th KDD},
 year = {2012},
 pages = {213--221},
 }
  
@article{jamianlp,
    author = {Banerjee, Imon and Li, Kevin and Seneviratne, Martin and Ferrari, Michelle and Seto, Tina and Brooks, James D and Rubin, Daniel L and Hernandez-Boussard, Tina},
    title = "{Weakly supervised natural language processing for assessing patient-centered outcome following prostate cancer treatment}",
    journal = {Journal of the American Medical Informatics Association Open},
    volume = {2},
    number = {1},
    pages = {150-159},
    year = {2019},
    }
    
@Article{dnaapp,
author="Chang, W. I.
and Lawler, E. L.",
title="Sublinear approximate string matching and biological applications",
journal="Algorithmica",
year="1994",
month="Nov",
day="01",
volume="12",
number="4",
pages="327--344"}

@Article{knnrtree,
author="B{\"o}hm, Christian
and Krebs, Florian",
title="The k-Nearest Neighbour Join: Turbo Charging the KDD Process",
journal="Knowledge and Information Systems",
year="2004",
day="01",
volume="6",
number="6",
pages="728--749",
}

@Article{shoppingpath,
author="Yada, Katsutoshi",
title="String analysis technique for shopping path in a supermarket",
journal="Journal of Intelligent Information Systems",
year="2011",
month="Jun",
day="01",
volume="36",
number="3",
pages="385--402",
}

@inproceedings{maxcfp,
author = {Jingbo Shang and Jian Peng and Jiawei Han},
title = {{MACFP}: Maximal Approximate Consecutive Frequent Pattern Mining under Edit Distance},
booktitle = {16th SDM},
pages = {558-566},
year={2016}
}

@article{DBLP:journals/siamcomp/Furer09,
  author    = {Martin F{\"{u}}rer},
  title     = {Faster Integer Multiplication},
  journal   = {{SIAM} J. Comput.},
  volume    = {39},
  number    = {3},
  pages     = {979--1005},
  year      = {2009},
  _url       = {https://doi.org/10.1137/070711761},
  _doi       = {10.1137/070711761},
  timestamp = {Sat, 27 May 2017 14:22:59 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/siamcomp/Furer09},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}
@ARTICLE{dpipaper,
author={Po-Ching Lin and Ying-Dar Lin and Yuan-Cheng Lai and Tsern-Huei Lee},
journal={{IEEE} {C}omputer},
title={Using String Matching for Deep Packet Inspection},
year={2008},
volume={41},
number={4},
pages={23-28}, 
}

@article{HUTCHINSON197580,
title = "On eulerian circuits and words with prescribed adjacency patterns",
journal = "Journal of Combinatorial Theory, Series A",
volume = "18",
number = "1",
pages = "80--87",
year = "1975",
issn = "0097-3165",
_doi = "https://doi.org/10.1016/0097-3165(75)90068-0",
_url = "http://www.sciencedirect.com/science/article/pii/0097316575900680",
author = "Joan P Hutchinson and Herbert S Wilf"
}

@article{DBLP:journals/tcs/FiciMRS06,
  author    = {Gabriele Fici and
               Filippo Mignosi and
               Antonio Restivo and
               Marinella Sciortino},
  title     = {Word assembly through minimal forbidden words},
  journal   = {Theoretical Computer Science},
  volume    = {359},
  number    = {1-3},
  pages     = {214--230},
  year      = {2006},
  _url       = {https://doi.org/10.1016/j.tcs.2006.03.006},
  _doi       = {10.1016/j.tcs.2006.03.006},
  timestamp = {Thu, 08 Jun 2017 09:02:47 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/tcs/FiciMRS06},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}


 year = {2014},
 isbn = {978-1-4503-2501-1},
IGNORElocation = {Kobe, Japan},
 pages = {296--303},
 numpages = {8},
IGNOREurl = {http://doi.acm.org/10.1145/2608628.2608664},
IGNOREdoi = {10.1145/2608628.2608664},
IGNOREacmid = {2608664},
IGNOREpublisher = {ACM},
IGNOREaddress = {New York, NY, USA},
} 

@inproceedings{Williams:2012:MMF:2213977.2214056,
 author = {Williams, Virginia Vassilevska},
 title = {Multiplying Matrices Faster Than {C}oppersmith-{W}inograd},
 booktitle = {44th STOC},
 year = {2012},
 pages = {887--898},
} 

@InProceedings{sse1,
author="Desmoulins, Nicolas
and Fouque, Pierre-Alain
and Onete, Cristina
and Sanders, Olivier",
title="Pattern Matching on Encrypted Streams",
booktitle="24th ASIACRYPT",
year="2018",
pages="121--148",
}

@proceedings{DBLP:conf/walcom/2015,
  editor    = {M. Sohel Rahman and
               Etsuji Tomita},
  title     = {{WALCOM:} Algorithms and Computation--9th International Workshop},
  series    = {Lecture Notes in Computer Science},
  volume    = {8973},
  publisher = {Springer},
  year      = {2015},
  _url       = {https://doi.org/10.1007/978-3-319-15612-5},
  _doi       = {10.1007/978-3-319-15612-5},
  isbn      = {978-3-319-15611-8},
  timestamp = {Tue, 14 May 2019 10:00:40 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/walcom/2015},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/siamcomp/GrossiV05,
  author    = {Roberto Grossi and
               Jeffrey Scott Vitter},
  title     = {Compressed Suffix Arrays and Suffix Trees with Applications to Text
               Indexing and String Matching},
  journal   = {{SIAM} J. Comput.},
  volume    = {35},
  number    = {2},
  pages     = {378--407},
  year      = {2005},
  _url       = {https://doi.org/10.1137/S0097539702402354},
  _doi       = {10.1137/S0097539702402354},
  timestamp = {Sat, 27 May 2017 14:22:59 +0200},
  biburl    = {https://dblp.org/rec/journals/siamcomp/GrossiV05.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{dcc19,
  author    = {Lorraine A. K. Ayad and
               Golnaz Badkobeh and
               Gabriele Fici and
               Alice H{\'{e}}liou and
               Solon P. Pissis},
  title     = {Constructing Antidictionaries in Output-Sensitive Space},
  booktitle = {{29th DCC}},
  pages     = {538--547},
  _publisher = {{IEEE}},
  year      = {2019}
}

@article{IC18,
  author    = {Panagiotis Charalampopoulos and
               Maxime Crochemore and
               Gabriele Fici and
               Robert Mercas and
               Solon P. Pissis},
  title     = {Alignment-free sequence comparison using absent words},
  journal   = {Inf. Comput.},
  volume    = {262},
  number    = {Part},
  pages     = {57--68},
  year      = {2018}
}

@article{DBLP:journals/iandc/CrochemoreHKMPR20,
  author    = {Maxime Crochemore and
               Alice H{\'{e}}liou and
               Gregory Kucherov and
               Laurent Mouchard and
               Solon P. Pissis and
               Yann Ramusat},
  title     = {Absent words in a sliding window with applications},
  journal   = {Inf. Comput.},
  volume    = {270},
  year      = {2020},
  _url       = {https://doi.org/10.1016/j.ic.2019.104461},
  _doi       = {10.1016/j.ic.2019.104461},
  timestamp = {Fri, 27 Mar 2020 08:40:29 +0100},
  biburl    = {https://dblp.org/rec/journals/iandc/CrochemoreHKMPR20.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/tcs/MignosiRS02,
  author    = {Filippo Mignosi and
               Antonio Restivo and
               Marinella Sciortino},
  title     = {Words and forbidden factors},
  journal   = {Theor. Comput. Sci.},
  volume    = {273},
  number    = {1-2},
  pages     = {99--117},
  year      = {2002},
  _url       = {https://doi.org/10.1016/S0304-3975(00)00436-9},
  _doi       = {10.1016/S0304-3975(00)00436-9},
  timestamp = {Sun, 28 May 2017 13:20:03 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/tcs/MignosiRS02},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{Silva02042015,
author = {Silva, Raquel~M. and Pratas, Diogo and Castro, Luísa and Pinho, Armando~J. and Ferreira, Paulo~J.~S.~G.}, 
title = {Three minimal sequences found in {E}bola virus genomes and absent from human {DNA}},
year = {2015},
volume = {31}, 
number = {15}, 
pages = {2421--2425}, 
journal = {Bioinformatics},
}

@article{10.1093/bioinformatics/btaa686,
    author = {Pratas, Diogo and Silva, Jorge M},
    title = "{Persistent minimal sequences of SARS-CoV-2}",
    journal = {Bioinformatics},
    year = {2020},
    month = {07},
    issn = {1367-4803},
    _doi = {10.1093/bioinformatics/btaa686},
    _url = {https://doi.org/10.1093/bioinformatics/btaa686},
    note = {btaa686},
    eprint = {https://academic.oup.com/bioinformatics/advance-article-pdf/doi/10.1093/bioinformatics/btaa686/33550747/btaa686.pdf},
}

@article{MAW,
	Author = {Carl Barton and Alice H\'{e}liou and Laurent Mouchard and Solon~P. Pissis},
	Journal = {BMC Bioinformatics},
	Pages = {388},
	Title = {Linear-time Computation of Minimal Absent Words Using Suffix Array},
	Volume = {15},
	Year = {2014}
    }
    
@article{minabpro,
	Author = {Sara~P. Garcia and O.~J. Pinho and Jo{\~a}o~M.~O.~S. Rodrigues and Carlos~A.~C. Bastos and Ferreira, Paulo~J.~S.~G.},
	Issue = {1},
	Journal = {PLoS ONE},
	Title = {Minimal Absent Words in Prokaryotic and Eukaryotic Genomes},
	Volume = {6},
	Year = {2011}}
	
@article{Chairungsee2012109,
	Author = {Supaporn Chairungsee and Maxime Crochemore},
	Journal = {Theoret. Comput. Sci.},
	Pages = {109-116},
	Title = {Using minimal absent words to build phylogeny},
	Volume = {450},
	Year = {2012}}

@article{FiReRi19,
author="Fici, Gabriele and Restivo, Antonio and Rizzo, Laura",
title="Minimal Forbidden Factors of Circular Words",
  journal   = {Theoret. Comput. Sci.},
volume = "792",
pages = "144--153",
year = "2019",
}

@inproceedings{DBLP:conf/isita/OtaM10,
  author    = {Takahiro Ota and
               Hiroyoshi Morita},
  title     = {On the adaptive antidictionary code using minimal forbidden words
               with constant lengths},
  booktitle = {{ISITA} 2010},
  pages     = {72--77},
  year      = {2010},
}

@ARTICLE{DCA,
author={Maxime Crochemore and Filippo Mignosi and Antonio Restivo and Sergio Salemi},
journal={Proceedings of the IEEE},
title={Data compression using antidictionaries},
year={2000},
_volume={88},
number={11},
pages={1756--1768},
_doi={10.1109/5.892711}}

@inproceedings{DBLP:conf/ppam/BartonHMP15,
  author    = {Carl Barton and
               Alice H{\'{e}}liou and
               Laurent Mouchard and
               Solon P. Pissis},
  title     = {Parallelising the Computation of Minimal Absent Words},
  booktitle = {11th
               {PPAM}. Revised Selected
               Papers, Part {II}},
  pages     = {243--253},
  year      = {2015},
}

@inproceedings{DBLP:conf/spire/FiciG19,
  author    = {Gabriele Fici and
               Pawel Gawrychowski},
  title     = {Minimal Absent Words in Rooted and Unrooted Trees},
  booktitle = {26th {SPIRE}},
  _series    = {Lecture Notes in Computer Science},
  _volume    = {11811},
  pages     = {152--161},
  publisher = {Springer},
  year      = {2019},
  _url       = {https://doi.org/10.1007/978-3-030-32686-9\_11},
  _doi       = {10.1007/978-3-030-32686-9\_11},
  timestamp = {Mon, 07 Oct 2019 12:13:46 +0200},
  biburl    = {https://dblp.org/rec/conf/spire/FiciG19.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{Crochemore98automataand,
	Author = {Maxime Crochemore and Filippo Mignosi and Antonio Restivo},
	Journal = {Information Processing Letters},
	Pages = {111--117},
	Title = {Automata and Forbidden Words},
	Volume = {67},
	Year = {1998}}
	
	@inproceedings{DBLP:conf/sofsem/MienoKAFNIBT20,
  author    = {Takuya Mieno and
               Yuki Kuhara and
               Tooru Akagi and
               Yuta Fujishige and
               Yuto Nakashima and
               Shunsuke Inenaga and
               Hideo Bannai and
               Masayuki Takeda},
  title     = {Minimal Unique Substrings and Minimal Absent Words in a Sliding Window},
  booktitle = {46th
               {SOFSEM}},
  _series    = {Lecture Notes in Computer Science},
  _volume    = {12011},
  pages     = {148--160},
  _publisher = {Springer},
  year      = {2020},
  _url       = {https://doi.org/10.1007/978-3-030-38919-2\_13},
  _doi       = {10.1007/978-3-030-38919-2\_13},
  timestamp = {Tue, 21 Jan 2020 16:23:04 +0100},
  biburl    = {https://dblp.org/rec/conf/sofsem/MienoKAFNIBT20.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}



@inproceedings{DBLP:conf/spire/Charalampopoulos18,
  author    = {Panagiotis Charalampopoulos and
               Maxime Crochemore and
               Solon P. Pissis},
  title     = {On Extended Special Factors of a Word},
  booktitle = {25th 
               {SPIRE}},
  pages     = {131--138},
  year      = {2018},
  _crossref  = {DBLP:conf/spire/2018},
  _url       = {https://doi.org/10.1007/978-3-030-00479-8\_11},
  _doi       = {10.1007/978-3-030-00479-8\_11},
  _timestamp = {Mon, 15 Jun 2020 17:12:49 +0200},
  _biburl    = {https://dblp.org/rec/conf/spire/Charalampopoulos18.bib},
  _bibsource = {dblp computer science bibliography, https://dblp.org}
}

@InProceedings{kosolobov_et_al:LIPIcs:2019:10484,
  author =	{Dmitry Kosolobov and Nikita Sivukhin},
  title =	{{Compressed Multiple Pattern Matching}},
  booktitle =	{30th CPM},
  pages =	{13:1--13:14},
  _series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  year =	{2019},
  _volume =	{128},
}


@inproceedings{DBLP:conf/mfcs/FujishigeTIBT16,
  author    = {Yuta Fujishige and
               Yuki Tsujimaru and
               Shunsuke Inenaga and
               Hideo Bannai and
               Masayuki Takeda},
  title     = {Computing DAWGs and Minimal Absent Words in Linear Time for Integer
               Alphabets},
  booktitle = {41st {MFCS}},
  _series    = {LIPIcs},
  _volume    = {58},
  pages     = {38:1--38:14},
  _publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2016},
  _url       = {https://doi.org/10.4230/LIPIcs.MFCS.2016.38},
  _doi       = {10.4230/LIPIcs.MFCS.2016.38},
  timestamp = {Sat, 30 May 2020 20:07:06 +0200},
  biburl    = {https://dblp.org/rec/conf/mfcs/FujishigeTIBT16.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{Garey:1978:SNR:322077.322090,
 author = {Garey, M. R. and Johnson, D. S.},
 title = {{``Strong''} {NP}-Completeness Results: Motivation, Examples, and Implications},
 journal = {J. ACM},
 _issue_date = {July 1978},
 volume = {25},
 number = {3},
 _month = jul,
 year = {1978},
 issn = {0004-5411},
 pages = {499--508},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/322077.322090},
 doi = {10.1145/322077.322090},
 acmid = {322090},
 publisher = {ACM},
 address = {New York, NY, USA},
} 
@misc{oldendata,
howpublished={\url{https://www.cs.utah.edu/~lifeifei/SpatialDataset.htm}}
}
@misc{dnadata,
howpublished={\url{http://bacteria.ensembl.org/Escherichia_coli_str_k_12_substr_mg1655/}}
}

@misc{trudata,
howpublished={\url{https://bitbucket.org/stringsanitization/stringsanitizationpkdd19/src/master/truck_char.txt}}
}
@misc{msndata,
howpublished={\url{http://archive.ics.uci.edu/ml/datasets/msnbc.com+anonymous+web+data}}
}
@misc{implempkdd,
howpublished={\url{https://bitbucket.org/stringsanitization/stringsanitizationpkdd19/src/master/}}
}

@inproceedings{fiot07,
  author    = {C. Fiot and
               A. Laurent and
               M. Teisseire},
  title     = {Approximate Sequential Patterns for Incomplete Sequence Database Mining},
  booktitle = {FUZZ},
  pages     = {1--6},
  year      = {2007},
}

@inproceedings{ragel,
author = {A. Ragel, A. and B. Cr\'{e}milleux},
title = {Treatment of Missing Values for Association Rules},
year = {1998},
booktitle = {2nd PAKDD},
pages = {258--270},
}

@inproceedings{calders,
author = {Calders, T. and Goethals, B. and Mampaey, M.},
title = {Mining Itemsets in the Presence of Missing Values},
year = {2007},
booktitle = {22nd SAC},
pages = {404--408},
}

@ARTICLE {puglisitkde,
author = {S. J. Puglisi and A. Turpin and J. Dhaliwal},
journal = {IEEE Transactions on Knowledge \& Data Engineering},
title = {Practical Efficient String Mining},
year = {2012},
volume = {24},
number = {04},
pages = {735-744},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}

@ARTICLE{ieeesp, author={E. {Bier} and R. {Chow} and P. {Golle} and T. H. {King} and J. {Staddon}}, journal={{IEEE} Secur. Priv.}, title={The Rules of Redaction: Identify, Protect, Review (and Repeat)}, year={2009}, volume={7}, number={6}, pages={46-53},} 

@Inbook{verykioschapter,
author="Verykios, Vassilios S.
and Gkoulalas-Divanis, Aris",
title="A Survey of Association Rule Hiding Methods for Privacy",
bookTitle="Privacy-Preserving Data Mining: Models and Algorithms",
year="2008",
publisher="Springer US",
address="Boston, MA",
pages="267--289",
isbn="978-0-387-70992-5",
doi="10.1007/978-0-387-70992-5_11",
url="https://doi.org/10.1007/978-0-387-70992-5_11"
}
@ARTICLE{aristkde, author={A. {Gkoulalas-Divanis} and V. S. {Verykios}}, journal={TKDE}, title={Exact Knowledge Hiding through Database Extension}, year={2009}, volume={21}, number={5}, pages={699-713},} 

@article{stavkais,
author = {Stavropoulos, E. C. and Verykios, V. S. and Kagklis, V.},
title = {A Transversal Hypergraph Approach for the Frequent Itemset Hiding Problem},
year = {2016},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
volume = {47},
number = {3},
issn = {0219-1377},
url = {https://doi.org/10.1007/s10115-015-0862-3},
doi = {10.1007/s10115-015-0862-3},
journal = {Knowl. Inf. Syst.},
month = jun,
pages = {625--645},
numpages = {21},
keywords = {Hiding frequent itemsets, Privacy-preserving data mining, Transversal hypergraph generation}
}

@inproceedings{kdd02,
author = {Ayres, Jay and Flannick, Jason and Gehrke, Johannes and Yiu, Tomi},
title = {Sequential PAttern Mining Using a Bitmap Representation},
year = {2002},
booktitle = {8th KDD},
pages = {429--435},
}

@book{statsbook,
author = {R. J. Little  and D. B. Rubin},
title = {Statistical Analysis with Missing Data (3rd ed.)},
year = {2019},
isbn = {0471802549},
publisher = {John Wiley \& Sons, Inc.},
address = {USA}
}

  @article{tukk,
  author    = {J. Tuikkala and
               L. Elo and
               O. Nevalainen and
               T. Aittokallio},
  title     = {Missing value imputation improves clustering and interpretation of
               gene expression microarray data},
  journal   = {{BMC} Bioinform.},
  volume    = {9},
  year      = {2008},
}

@inproceedings{dong,
author = {B. Dong and S. Xie and J. Gao and W. Fan and P. S. Yu},
title = {OnlineCM: Real-time Consensus Classification with Missing Values},
booktitle = {15th SDM},
pages = {685-693},
year={2015}
}

@inproceedings{cikm18imputation,
author = {F. Biessmann and D. Salinas and S. Schelter and P. Schmidt and D. Lange},
title = {“Deep” Learning for Missing Value Imputationin Tables with Non-Numerical Data},
year = {2018},
isbn = {9781450360142},
booktitle = {27th CIKM},
pages = {2017--2025},
}

@article{pvldb17imputation,
author = {J. Cambronero and J. K. Feser and M. J. Smith and S. Madden},
title = {Query Optimization for Dynamic Imputation},
year = {2017},
publisher = {VLDB Endowment},
volume = {10},
number = {11},
journal = {Proc. VLDB Endow.},
pages = {1310--1321},
numpages = {12}
}
 
@inproceedings{gis,
author = {J. J. Ying and W. Lee and T. Weng and V. S. Tseng},
title = {Semantic Trajectory Mining for Location Prediction},
year = {2011},
booktitle = {19th SIGSPATIAL},
pages = {34--43},
}
  
@INPROCEEDINGS{agrawal95, author={R. {Agrawal} and R. {Srikant}}, booktitle={11th ICDE}, title={Mining sequential patterns}, year={1995}, volume={}, number={}, pages={3-14}} 

@book{nello07,
  author    = {N. Cristianini and
               M. W. Hahn},
  title     = {Introduction to computational genomics - a case studies approach},
  publisher = {Cambridge University Press},
  year      = {2007}
}

@InProceedings{missingbasic,
author="J. W. Grzymala-Busse and M. Hu",
title="A Comparison of Several Approaches to Missing Attribute Values in Data Mining",
booktitle="3rd  RSCTC",
year="2001",
pages="378--385",
}

@article{saygin,
author = {Saygin, Y\"{u}cel and Verykios, Vassilios S. and Clifton, Chris},
title = {Using Unknowns to Prevent Discovery of Association Rules},
year = {2001},
publisher = {Association for Computing Machinery},
volume = {30},
number = {4},
journal = {SIGMOD Rec.},
pages = {45--54},
numpages = {10}
}

  

@article{bioinf14,
    author = {Roy, Rajat Shuvro and Bhattacharya, Debashish and Schliep, Alexander},
    title = "{ Turtle: Identifying frequent k -mers with cache-efficient algorithms }",
    journal = {Bioinformatics},
    volume = {30},
    number = {14},
    pages = {1950-1957},
    year = {2014},
}

@article{is15,
author = {Chen, M. and Yu, X. and Liu, Y.},
title = {Mining Moving Patterns for Predicting next Location},
year = {2015},
_issue_date = {December 2015},
publisher = {Elsevier Science Ltd.},
volume = {54},
number = {C},
pages = {156--168},
numpages = {13},

}

@INPROCEEDINGS{webputicde19, author={S. {Shan} and Z. {Li} and Y. {Li} and Q. {Yang} and J. {Zhu} and M. {Sharaf} and X. {Zhou}}, booktitle={35th ICDE}, title={WebPut: A Web-Aided Data Imputation System for the General Type of Missing String Attribute Values}, year={2019}, volume={}, number={}, pages={1952-1955},} 

@inproceedings{sdm16,
  author    = {J. Shang and
               J. Peng and
               J. Han},
  editor    = {Sanjay Chawla Venkatasubramanian and
               Wagner Meira Jr.},
  title     = {{MACFP:} Maximal Approximate Consecutive Frequent Pattern Mining under
               Edit Distance},
  booktitle = {16th SDM},
  pages     = {558--566},
  year      = {2016},
}

@article{acmjqual19,
author = {A. Lazar and L. Jin and A. C. Spurlock and K.  Wu and A. Sim and A. Todd},
title = {Evaluating the Effects of Missing Values and Mixed Data Types on Social Sequence Clustering Using T-SNE Visualization},
year = {2019},
volume = {11},
number = {2},
journal = {J. Data and Information Quality},
}

  
  
@ARTICLE{tkde20, author={B. {Gu} and Z. {Li} and A. {Liu} and J. {Xu} and L. {Zhao} and X. {Zhou}}, journal={IEEE Transactions on Knowledge and Data Engineering}, title={Improving the Quality of Web-based Data Imputation with Crowd Intervention}, year={2019}, volume={}, number={}, pages={1-1},} 

@inproceedings{hirs,
    title = "Measuring Risk and Information Preservation: Toward New Metrics for De-identification of Clinical Texts",
    author = "Hirschman, Lynette  and
      Aberdeen, John",
    booktitle = "2nd Louhi Workshop on Text and Data Mining of Health Documents",
    year = "2010",
    publisher = "Association for Computational Linguistics",
    pages = "72--75",
}

@article{pisinger,
  author    = {David Pisinger},
  title     = {A Minimal Algorithm for the Bounded Knapsack Problem},
  journal   = {{INFORMS} Journal on Computing},
  volume    = {12},
  number    = {1},
  pages     = {75--82},
  year      = {2000},
}

@article{DBLP:journals/jc/JohnsonG85,
  author    = {David S. Johnson and
               M. R. Garey},
  title     = {A 71/60 theorem for bin packing},
  journal   = {J. Complex.},
  volume    = {1},
  number    = {1},
  pages     = {65--106},
  year      = {1985},
}

@article{carrell,
  author    = {David Carrell and
               Bradley A. Malin and
               John S. Aberdeen and
               Samuel Bayer and
               Cheryl Clark and
               Ben Wellner and
               Lynette Hirschman},
  title     = {Hiding in plain sight: use of realistic surrogates to reduce exposure
               of protected health information in clinical text},
  journal   = {{JAMIA}},
  volume    = {20},
  number    = {2},
  pages     = {342--348},
  year      = {2013},
}

@article{lenstra,
author = {Lenstra, H. W.},
title = {Integer Programming with a Fixed Number of Variables},
journal = {Mathematics of Operations Research},
volume = {8},
number = {4},
pages = {538-548},
year = {1983},
}

@InProceedings{eisenbrand,
author="Eisenbrand, Friedrich",
editor="Di Battista, Giuseppe
and Zwick, Uri",
title="Fast Integer Programming in Fixed Dimension",
booktitle="11th ESA",
year="2003",
publisher="Springer Berlin Heidelberg",
pages="196--207",
}

@article{megiddo,
author = {N. Megiddo},
title = {Linear Programming in Linear Time When the Dimension Is Fixed},
year = {1984},
volume = {31},
number = {1},
journal = {J. ACM},
pages = {114--127},
numpages = {14}
}

@article{DBLP:journals/bioinformatics/LiD10,
  author    = {H. Li and
               R. Durbin},
  title     = {Fast and accurate long-read alignment with Burrows-Wheeler transform},
  journal   = {Bioinform.},
  volume    = {26},
  number    = {5},
  pages     = {589--595},
  year      = {2010},
}

@article{DBLP:journals/bioinformatics/LiYLLYKW09,
  author    = {R. Li and
               C. Yu and
               Y. Li and
               T. Wah Lam and
               S. Yiu and
               K. Kristiansen and
               J. Wang},
  title     = {{SOAP2:} an improved ultrafast tool for short read alignment},
  journal   = {Bioinformatics},
  volume    = {25},
  number    = {15},
  pages     = {1966--1967},
  year      = {2009}
}

@book{DBLP:books/sp/fpm2014,
  author    = {W. Shen and
               J. Wang and
               J. Han},
  title     = {Sequential Pattern Mining},
  booktitle = {Frequent Pattern Mining},
  pages     = {261--282},
  year      = {2014},
    publisher = {Springer},
}

@proceedings{DBLP:conf/focs/1997,
  title     = {38th FOCS},
  publisher = {{IEEE} Computer Society},
  year      = {1997},
}

@inproceedings{Ruzic08,
  author    = {Milan Ruzic},
  title     = {Constructing Efficient Dictionaries in Close to Sorting Time},
  booktitle = {35th {ICALP}},
  volume    = {5125},
  pages     = {84--95},
  publisher = {Springer},
  year      = {2008}
}

@article{tcsmax,
  author    = {Maria Federico and
               Nadia Pisanti},
  title     = {Suffix tree characterization of maximal motifs in biological sequences},
  journal   = {Theor. Comput. Sci.},
  volume    = {410},
  number    = {43},
  pages     = {4391--4401},
  year      = {2009}
}

@article{DBLP:journals/nar/Martinez83,
  author    = {H. M. Martinez},
  title     = {An efficient method for finding repeats in molecular sequences},
  journal   = {Nucleic Acids Research},
  volume    = {11},
  number    = {13},
  pages     = {4629--4634},
  year      = {1983},
  }

@article{motifs4tfbs,
  author    = {L. Marsan and
               M. Sagot},
  title     = {Algorithms for Extracting Structured Motifs Using a Suffix Tree with
               an Application to Promoter and Regulatory Site Consensus Identification},
  journal   = {J. Comput. Biol.},
  volume    = {7},
  number    = {3-4},
  pages     = {345--362},
  year      = {2000}
}

@article{DBLP:journals/nar/SinhaT03,
  author    = {Saurabh Sinha and
               Martin Tompa},
  title     = {{YMF:} a program for discovery of novel transcription factor binding
               sites by statistical overrepresentation},
  journal   = {Nucleic Acids Research},
  volume    = {31},
  number    = {13},
  pages     = {3586--3588},
  year      = {2003},
}



@article{motifs,
    author = {Keich, U. and Pevzner, P. A.},
    title = "{Finding motifs in the twilight zone}",
    journal = {Bioinformatics},
    volume = {18},
    number = {10},
    pages = {1374-1381},
    year = {2002},
}

 @InProceedings{myrapkdd,
author="M. Spiliopoulou",
_editor="{J. M. \.{Z}}ytkow 
and J. Rauch",
title="Managing Interesting Rules in Sequence Mining",
booktitle="3rd PKDD",
year="1999",
pages="554--560",
}

@article{DBLP:jmotex,
  author    = {S. P. Pissis},
  title     = {MoTeX-II: structured MoTif eXtraction from large-scale datasets},
  journal   = {{BMC} Bioinform.},
  volume    = {15},
  pages     = {235},
  year      = {2014},
}


@article{Rayan,
    author = {S. Rangavittal and R. S. Harris and  M. Cechova and M. Tomaszkiewicz and R. Chikhi and  K. D. Makova and P. Medvedev},
    title = "{RecoverY: k-mer-based read classification for Y-chromosome-specific sequencing and assembly}",
    journal = {Bioinformatics},
    volume = {34},
    number = {7},
    pages = {1125-1131},
    year = {2017},
    _month = {11},
}

  @inproceedings{guralnik,
  author    = {V. Guralnik and
               G. Karypis},
  title     = {A Scalable Algorithm for Clustering Sequential Data},
  booktitle = {1st ICDM},
  pages     = {179--186},
  year      = {2001},
}

@ARTICLE{xiongtkde16, author={S. {Xu} and X. {Cheng} and S. {Su} and K. {Xiao} and L. {Xiong}}, journal={TKDE}, title={Differentially Private Frequent Sequence Mining}, year={2016}, volume={28}, number={11}, pages={2910-2926},} 

@article{monreale,
author = {Monreale, Anna and Pedreschi, Dino and Pensa, Ruggero G. and Pinelli, Fabio},
title = {Anonymity Preserving Sequential Pattern Mining},
year = {2014},
publisher = {Kluwer Academic Publishers},
volume = {22},
number = {2},
journal = {Artif. Intell. Law},
pages = {141--173},
numpages = {33},
}

@article{locations,
  title={Apriori-based algorithms for km-anonymizing trajectory data},
  author={G. Poulis and S. Skiadopoulos and G. Loukides and A. Gkoulalas-Divanis},
  journal={Trans. Data Privacy},
  year={2014},
  volume={7},
  pages={165-194}
}


@article{DBLP:journals/tcs/AlmirantisCGIMP19,
  author    = {Yannis Almirantis and
               Panagiotis Charalampopoulos and
               Jia Gao and
               Costas S. Iliopoulos and
               Manal Mohamed and
               Solon P. Pissis and
               Dimitris Polychronopoulos},
  title     = {On overabundant words and their application to biological sequence
               analysis},
  journal   = {Theor. Comput. Sci.},
  volume    = {792},
  pages     = {85--95},
  year      = {2019},
}
@ARTICLE{wutkde, author={Y. {Wu} and C. {Chiang} and A. L. P. {Chen}}, journal={TKDE}, title={Hiding Sensitive Association Rules with Limited Side Effects}, year={2007}, volume={19}, number={1}, pages={29-42},} 


@article{DBLP:journals/eor/AndonovPR00,
  author    = {Rumen Andonov and
               Vincent Poirriez and
               Sanjay V. Rajopadhye},
  title     = {Unbounded knapsack problem: Dynamic programming revisited},
  journal   = {Eur. J. Oper. Res.},
  volume    = {123},
  number    = {2},
  pages     = {394--407},
  year      = {2000},
}


@inproceedings{DBLP:conf/icalp/CrochemoreMRS99,
  author    = {M. Crochemore and
               F. Mignosi and
               A. Restivo and
               S. Salemi},
  title     = {Text Compression Using Antidictionaries},
  booktitle = {26th ICALP},
  pages     = {261--270},
  year      = {1999},
    volume    = {1644},
}

@inproceedings{DBLP:conf/sdm/LiBKP14,
  author    = {Yuxuan Li and
               James Bailey and
               Lars Kulik and
               Jian Pei},
  title     = {Efficient Matching of Substrings in Uncertain Sequences},
  booktitle = {14th SDM},
  pages     = {767--775},
  year      = {2014},
}

@inproceedings{bonomicikm,
author = {Bonomi, Luca and Xiong, Li},
title = {A Two-Phase Algorithm for Mining Sequential Patterns with Differential Privacy},
year = {2013},
booktitle = {22nd CIKM},
pages = {269--278},
}

@book{PC,
author = {M. Cygan and F. V. Fomin and  L. Kowalik and D. Lokshtanov and D. Marx and M. Pilipczuk and M. Pilipczuk and S. Saurabh},
title = {Parameterized Algorithms},
year = {2015},
publisher = {Springer Publishing Company, Incorporated},
edition = {1st}
}

@ARTICLE{NGS,
author={D. C. Koboldt and K. M. Steinberg and David E. Larson and Richard K. Wilson and Elaine R. Mardis},
journal={Cell},
title={The Next-Generation Sequencing Revolution and Its Impact on Genomics},
year={2013},
volume={155},
number={1},
pages={27-38} 
}