Abstract
This paper tells the story of the Four Schools of Amathus and the lost recipes for a legendary dish that attracted many people to the ancient royal city. Deciphering the recipes from snippets of the ancient scrolls that have been found recently seems to be an impossible task. Fortunately, the problem bears a strong resemblance to the haplotype phasing problem, which has been studied in more recent times. We point out the similarities between these problems, how they can be formulated as optimization problems and survey different solution strategies.
Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 395192176.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bonizzoni, P., Dondi, R., Klau, G.W., Pirola, Y., Pisanti, N., Zaccaria, S.: On the minimum error correction problem for haplotype assembly in diploid and polyploid genomes. J. Comput. Biol. 23(9), 718–736 (2016)
Cilibrasi, R., van Iersel, L., Kelk, S., Tromp, J.: On the complexity of several haplotyping problems. In: Casadio, R., Myers, G. (eds.) WABI 2005. LNCS, vol. 3692, pp. 128–139. Springer, Heidelberg (2005). https://doi.org/10.1007/11557067_11
Klau, G.W., Marschall, T.: A guided tour to computational haplotyping. In: Kari, J., Manea, F., Petre, I. (eds.) CiE 2017. LNCS, vol. 10307, pp. 50–63. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58741-7_6
Lippert, R., Schwartz, R., Lancia, G., Istrail, S.: Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem. Briefings Bioinf. 3(1), 23–31 (2002)
Martin, M., et al.: WhatsHap: fast and accurate read-based phasing. bioRxiv (2016). https://doi.org/10.1101/085050, https://www.biorxiv.org/content/early/2016/11/14/085050
Motazedi, E., Finkers, R., Maliepaard, C., de Ridder, D.: Exploiting next generation sequencing to solve the haplotyping puzzle in polyploids: a simulation study. Briefings Bioinf. 19(3), 387–403 (2018)
Patterson, M., et al.: WhatsHap: weighted haplotype assembly for future-generation sequencing reads. J. Comput. Biol. 22(6), 498–509 (2015)
Pirola, Y., Zaccaria, S., Dondi, R., Klau, G.W., Pisanti, N., Bonizzoni, P.: HapCol: accurate and memory-efficient haplotype assembly from long reads. Bioinformatics 32(11), 1610–1617 (2015). (Oxford, England)
Schrinner, S.D., et al.: Haplotype threading: accurate polyploid phasing from long reads (2019, in preparation)
Acknowledgments
I wish to thank all the co-authors of the various papers on haplotype phasing mentioned in Sect. 3, especially Sven Schrinner and Tobias Marschall, Jana Ebler and Rebecca Serra Mari for the nice collaboration on the polyploid phasing problem. Thanks to Philipp Spohr for inspirations shaping the Amathus story and to Nguyen Khoa Tran for providing the beautiful drawing of Athena, Barnabas, Charalambos and Daphne.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Klau, G.W. (2020). The Lost Recipes from the Four Schools of Amathus. In: Chatzigeorgiou, A., et al. SOFSEM 2020: Theory and Practice of Computer Science. SOFSEM 2020. Lecture Notes in Computer Science(), vol 12011. Springer, Cham. https://doi.org/10.1007/978-3-030-38919-2_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-38919-2_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-38918-5
Online ISBN: 978-3-030-38919-2
eBook Packages: Computer ScienceComputer Science (R0)