Mutatais in the Software Libraries Industry

Mutata

mutata

The following piece claims to reduce an artist's cognitive overload in graphics design software using a simplified digital compositing node graph aka Pipeline. Proceed at your own risk. Content Overview An Example of Cognitive Overload A Mad Proposal A Mad Comparison to Digital Compositing Node Graph What Changed? Nothing, Really An Insane User Interface Then, things Start to get Crazier Digital Compositing Paradigm in a Pipeline Omg! Advantages. Lol! You must be Mad too An Example of Cognitive Overload Imagine a graphic artist performing a series of photo edits: 1. Apply Disc Blur to an image.
2. Apply Sepia Tone to Disc Blur.
3. Blend the Sepia Tone with the original. The intent of the artist usually consists of a sequence of actions to be translated into operations  carried out with the graphics software. For example, the process of the photo edits above may involve creating a new document, selecting the optimal image options in the application menu, creating Layers to apply a Disc Blur, changing properties in a side panel, bringing up an object dialog box, and repeating the process to add additional layers for the Sepia Tone/Blend to achieve the desired effect. This approach of user interface and when exacerbated with an increasing number of steps results in and . NON-STREAMLINED disrupts the flow of thoughts of the artist Cognitive Overload loss of creative productivity We are OK with the above. What's WRONG? A Mad Proposal We the user interface into a linear sequence of actions that can be compounded or stacked like a digital compositing node graph but with simplification to express how to achieve the desired outcome succinctly, like below: streamline Pipeline

1. Read Image
2. Disc Blur
3. Sepia Tone
4. Blend (2,3) A Pipeline is to the user interface of graphics design software like what Markdown is to HTML. A Mad Comparison to Digital Compositing Node Graph To someone familiar with Digital Compositing, they will immediately recognize that the list of steps, the Pipeline, above is "almost" identical to a digital compositing node graph. A digital compositing node graph is shown below: Read Image
|         |
|         |
|         V
|         Disc Blur
|         |
|         |
|         V
|         Sepia Tone
|         |
|         |
V         V
   Blend What Changed? Nothing, Really A Pipeline is indeed similar to a digital compositing node graph with a subtle yet significant change. Instead of displaying a full node graph graphically, with two lines from the Read Image node and Sepia Tone node connecting to the Blend node. The Pipeline simplifies the node graph by just showing a list of steps and a spreadsheet-like function for the final Blend step. 4. Blend (2,3) This creativity of arranging a digital compositing node graph as a Pipeline enables the intent of the artist to be conveyed as a succinct list of steps, following the artist's flow of thoughts from start to end, without a graphical map. The Pipeline also guides the artist into thinking of what to do next in a streamlined manner. Without using a traditional node graph, more information can be conveyed in a smaller amount of space linearly, providing a larger contextual overview to the creative mind. An Insane User Interface A Pipeline, in software, maps directly to a list and is easy to implement. The list removes the need for a complicated graphical map that may require (scrolling) to identify the right node to work on. The properties screen of a node can also be brought up intuitively and naturally by drilling into the node. panning Pipeline

1. Read Image
2. Disc Blur  ----> Drill into the Properties screen
3. Sepia Tone
4. Blend (2,3) PROTOTYPE - Fits into a mobile phone Then, Things Start to get Crazier No loss of information The important thing to note is the above creativity does not lose any information. The simplified node graph above, the Pipeline, in a mathematical sense, can be fully represented as a node graph (Directed Acyclic Graph) in any manner or form. For example, if we have the following node graph for video processing. Read media Read media 
|          |
V          V
Premult    Color Correction 
|          |
|          V 
|          Transform 
|          |
|          V 
|          Gaussian Blur 
|          | 
V          V 
Merge 
|
V 
Viewer It can be flattened, streamlined, and represented as follows: Read media
|
V
Premult

Read media
|
V
Color Correction
|
V
Transform
|
V
Gaussian Blur

Merge
|
V
Viewer Note the break from the first series after the 'Premult' node and the second break after the 'Gaussian Blur' node. Pipeline

1. Read media         >
2. Premult            >

3. Read media         >
4. Color Correction   >
5. Transform          >
6. Blur               >

7. Merge (2,6)        >
8. Viewer             > The space between node 2 and node 3 represents the break, while the '>' is optional and used to indicate the availability of a properties screen. Digital Compositing Paradigm in a Pipeline The paradigm of node-based digital compositing where we can lay out steps in a progression and make modifications to an earlier step to change the outcome is completely kept. Each node can be easily reused by referencing it with a node number as in Step 7, and if required, used further in a later step, saving time and effort. In the same way that a digital compositing node graph is broken into a series of nodes in a graph, a Pipeline breaks it into a series of actions or steps. A Pipeline, from another angle, is thus like a single-column spreadsheet, a metaphor that many computer users are quite familiar with. Viewing the output of each step: Viewer Cycling The arrangement in a series of steps enables the output of each progression step to be viewed easily, for example, by long pressing on a node on the Pipeline. This enables an artist to step through the progression to reinforce his or her cognitive working memory of what has been performed. Connecting the steps: Auto-Chaining Each node on the Pipeline that requires an input can be assumed to be taking the output of the previous node automatically. For example, the 'Premult' node in Step 2 is assumed to automatically take the output from 'Read Media' in Step 1. Connecting the steps like a node graph: Reverse Compositing The auto-chaining or automatic preceding node referencing behavior can also be altered by enabling the artist to make changes in the properties of a node. For example, in Step 7, the artist can choose from its properties screen any of the previous nodes, such as nodes 2 and 6, for blending. Omg! Advantages. Lol! Modular Extensibility A Pipeline, being almost identical to a digital compositing node graph, enables it to achieve the same modular extensibility in software development. Software developers can think of developing graphical effects, filters, animations, and 3D operations modularly as a node. Each node is accompanied by a properties user interface that does not interfere with other parts of the software. A node and its user interface can thus be developed and tested independently while knowing ultimately that it can be easily integrated into a full node graph, aka the Pipeline, to achieve any complex graphics operation. Such a design will benefit the open-source community greatly where many different developers can build an open-source Pipeline, the Open Pipeline, together in a distributed and collaborative manner. Reduce Information Overload To start using a graphics application, artists usually need to learn the way of achieving it through documentation. Often, the documentation requires an artist to follow a series of screenshots, explaining where and how to click or tap on different parts of the screen using a non-streamlined user interface offered by the graphics application. The non-streamlined user interface makes the information hard for an artist to remember and may require the artist to constantly refer to the documentation. Over time, this introduces an additional cost that, when accumulated, can lead to . Information Overload Succinct Self-Describing Pipeline The Open Pipeline reduces Information Overload as it succinctly describes what needs to be done and allows all necessary details to be shown in context nearby. This significantly benefits documentation: tutorials, articles, or books. Open Pipeline

1. Disc Blur: radius = 8
2. Sepia Tone: intensity = 1
3. Blend (1,2) The details of the radius for Disc Blur are shown as part of the node in the Pipeline. Moreover, besides being , it is common for the above description to supporting screenshots as it is self-explanatory. succinct NOT REQUIRE You must be Mad too If you have followed this article till here, find out more about the author's banishment due to his 'NOT SO' , and where he is living in exile. His ‘BLUFF’ of implementing a node that ‘CAN BE INTEGRATED EASILY’ into the Pipeline. And him performing a MAGIC TRICK. REALLY. He compares himself with the Roman poet Ovid by quoting on ‘how shapes changed into new bodies’ in Metamorphoses: Open Pipeline Photo Curve Photo Fire Effect – OVID In nova fert animus mutatas dicere formas corpora; di, coeptis (nam vos mutastis et illas) adspirate meis primaque ab origine mundi ad mea perpetuum deducite tempora carmen. Sigh, I give up He further mumbles about animating a graphics object with a node. METAMORPHOSIS The lead image for this article was generated by HackerNoon's AI Image Generator via the prompt "cognitive overload".

Revolutionary User Interface Design: Tackling Cognitive Overload in Graphics Software

Insect Adventures by Jean-Henri Fabre and Louise Hasbrouck Zimm, is part of the HackerNoon Books Series. You can jump to any chapter in this book here . THE GEOMETRY OF THE SPIDER’S WEB CHAPTER XXV. THE GEOMETRY OF THE SPIDER’S WEB [This chapter, one of the most wonderful in Fabre’s books, is included in a simplified form in this volume, on account of its interest to such younger readers as have studied geometry.] WHEN we look at the webs of the Garden Spiders, especially those of the Silky Spider and the Banded Spider, we notice first that the spokes or radii are equally spaced; the angles formed by each consecutive pair are of the same value; and this in spite of their number, which in the webs of the Silky Spider sometimes exceeds forty. We know in what a strange way the Spider weaves her web and divides the area of the web into a large number of equal parts or sectors, a number which is almost always the same in the work of each species of Spider. The Spider darts here and there when laying her spokes as if she had no plan, and this irresponsible way of working produces a beautiful web like the rose-window in a church, a web which no designer could have drawn better with compasses. We shall also notice that, in each sector, the various chords, parts of the angular spiral, are parallel to one another and gradually draw closer together as they near the center. With the two radiating lines that frame them they form obtuse angles on one side and acute angles on the other; and these angles remain constant in the same sector, because the chords are parallel. There is more than this: these same angles, the obtuse as well as the acute, do not alter in value, from one sector to another, as far as the eye can judge. Taken as a whole, therefore, the spiral consists of a series of cross-bars intersecting the several radiating lines obliquely at angles of equal value. By this characteristic we recognize what geometricians have named the “logarithmic spiral.” It is famous in science. The logarithmic spiral describes an endless number of circuits around its pole, to which it constantly draws nearer without ever being able to reach it. We could not see such a line, the whole of it, even with our best philosophical instruments. It exists only in the imagination of scientists. But the Spider knows it, and winds her spiral in the same way, and very accurately at that. Another property of this spiral is that if one in imagination winds a flexible thread around it, then unwinds the thread, keeping it taut the while, its free end will describe a spiral similar at all points to the original. The curve will merely have changed places. Jacques Bernouilli, the professor of mathematics who discovered this magnificent theorem, had engraved on his tomb, as one of his proudest titles to fame, the spiral and its double, made by the unwinding of the thread. Written underneath it was the sentence: Eadem mutata resurgo. “I rise again like unto myself.” It was a splendid flight of fancy which showed his belief in immortality. Now is this logarithmic spiral, with its curious properties, merely an idea of the geometricians? Is it a mere dream, an abstract riddle? No, it is a reality in the service of life, a method of construction often employed by animals in their architecture. The Mollusk never makes its shell without reference to the scientific curve. The first-born of the species knew it and put it into practice; it was as perfect in the dawn of creation as it can be to-day. There are perfect examples of this spiral found in the shells of fossils. To this day, the last representative of an ancient tribe, the Nautilus of the Southern Seas, remains faithful to the old design, and still whirls its spiral logarithmically, as did its ancestors in the earliest ages of the world’s existence. Even in the stagnant waters of our grassy ditches, a tiny Shellfish, no bigger than a duckweed, rolls its shell in the same manner. The common snail-shell is constructed according to logarithmic laws. Where do these creatures pick up this science? We are told that the Mollusk is descended from the Worm. One day the Worm, rendered frisky by the sun, brandished its tail and twisted it into a corkscrew for sheer glee. There and then the plan of the future spiral shell was discovered. This is what is taught quite seriously, in these days, as the very last word in science. But the Spider will have none of this theory. For she is not related to the Worm; and yet she is familiar with the logarithmic spiral and uses it in her web, in a simpler form. The Mollusk has years in which to build her spiral, so she makes it very perfectly. The Spider has only an hour at the most to spread her net, so she makes only a skeleton of the curve; but she knows the same line dear to the Snail. What guides her? Nothing but an inborn skill, whose effects the animal is no more able to control than the flower is able to control the arrangement of its petals and stamens. The Spider practices higher geometry without knowing or caring. The thing works of itself and takes its way from an instinct imposed upon creation at the start. The stone thrown by the hand returns to earth describing a certain curve; the dead leaf torn and wafted away by a breath of wind makes its journey from the tree to the ground with a similar curve. The curve is known to science and is called the “parabola.” The geometricians speculate still more about this curve; they imagine it rolling on an indefinite straight line and ask what course the focus of the curve follows. The answer comes that the focus of the parabola describes a “catenary,” a line whose algebraic symbol is so complicated that a numeral will not express it. The nearest it can get is this terrible sum: The geometricians do not attempt to refer to it by this number; they give it a letter, e. Is this line imaginary? Not at all; you may see the catenary frequently. It is the shape taken by a flexible cord when held at each end and relaxed; it is the line that governs the shape of a sail filled out by the wind. All this answers to the number e. What a quantity of abstruse science for a bit of string! Let us not be surprised. A pellet of shot swinging at the end of a thread, a drop of dew trickling down a straw, a splash of water rippling under the kisses of the air, a mere trifle, after all, becomes tremendously complicated when we wish to examine it with the eye of calculation. We need the club of Hercules to crush a fly. Our methods of mathematical investigation are certainly ingenious; we cannot too much admire the mighty brains that have invented them; but how slow and laborious they seem when compared with the smallest actual things! Shall we never be able to inquire into reality in a simpler fashion? Shall we be intelligent enough some day to do without all these heavy formulæ? Why not? Here we have the magic number e reappearing, written on a Spider’s thread. On a misty morning the sticky threads are laden with tiny drops, and, bending under the burden, have become so many catenaries, so many chains of limpid gems, graceful chaplets arranged in exquisite order and following the curve of a swing. If the sun pierce the mist, the whole lights up with rainbow-colored fires and becomes a dazzling cluster of diamonds. The number e is in its glory. Geometry, that is to say, the science of harmony in space, rules over everything. We find it in the arrangement of the scales of a fir-cone, as in the arrangement of a Spider’s sticky snare; we find it in the spiral of a snail-shell, in the chaplet of a Spider’s thread, as in the orbit of a planet; it is everywhere, as perfect in the world of atoms as in the world of immensities. And this universal geometry tells us of a Universal Geometrician, whose divine compass has measured all things. I prefer that, as an explanation of the logarithmic curve of the Nautilus and the Garden Spiders, to the Worm screwing up the tip of its tail. It may not perhaps be in agreement with some latter-day teaching, but it takes a loftier flight. About HackerNoon Book Series: We bring you the most important technical, scientific, and insightful public domain books. This book is part of the public domain. Jean-Henri Fabre and Louise Hasbrouck Zimm (2014). Insect Adventures. Urbana, Illinois: Project Gutenberg. Retrieved October https://www.gutenberg.org/cache/epub/45812/pg45812-images.html This eBook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever. You may copy it, give it away or re-use it under the terms of the Project Gutenberg License included with this eBook or online at www.gutenberg.org , located at https://www.gutenberg.org/policy/license.html .

THE GEOMETRY OF THE SPIDER’S WEB

THE GEOMETRY OF THE EPEIRA’S WEB

SECONDARY SEXUAL CHARACTERS OF MAN

This paper is available on under CC 4.0 license. Arxiv Authors: (1) Md Masud Rana, Department of Mathematics, University of Kentucky; (2) Duc Duy Nguyen, Department of Mathematics, University of Kentucky & ducnguyen@uky.edu. Table of Links Abstract & Introduction Datasets and Results Methods Conclusion, Data and Software Availability, Competing interests, Acknowledgments & References 4 Conclusion The study of protein-protein interactions (PPIs) and the prediction of mutation-induced binding free energy changes are of great importance in understanding the molecular basis of biological processes. The application of geometric graph theory and atom-level graph coloring techniques provides a powerful framework for analyzing biomolecules and capturing their intricate relationships. By utilizing the concept of geometric subgraphs and constructing multi-scale weighted colored geometric subgraphs (MWCGS), we can effectively represent the structural and functional properties of PPIs. The site-specific MWCGS features allow us to extract meaningful patterns and characteristics, shedding light on the effects of mutations and the underlying molecular interactions. In this work, we developed a mutation-induced binding free energy change predictor, called GGL-PPI, by incorporating site-specific MWCGS features for PPIs and gradient-boosting trees. Our method demonstrates superior performance compared to existing methods. The model was validated on three datasets: AB-Bind S645, SKEMPI 1.0 S1131, and SKEMPI 2.0 S4169 and S8338, showcasing its robustness and effectiveness. Furthermore, GGL-PPI was evaluated on a blind test set, the Ssym dataset. To prevent data leakage between the test and training sets, the model was trained on a homology-reduced balanced training set Q3488. This approach ensures the reliability and fairness of the evaluation process. GGL-PPI exhibits the most unbiased and superior performance in predicting binding free energy changes for both direct and reverse mutations, outperforming other existing methods, particularly for reverse mutations. Overall, the results highlight the potential of the GGL-PPI approach in accurately predicting mutation-induced binding free energy changes in protein-protein interactions, providing valuable insights into the molecular mechanisms underlying protein-protein interactions and facilitating drug design and discovery efforts. 5 Data and Software Availability The source code is available at Github: https://github.com/NguyenLabUKY/GGL-Mutation. 6 Competing interests No competing interest is declared. 7 Acknowledgments This work is supported in part by funds from the National Science Foundation (NSF: # 2053284, # 2151802, and # 2245903), and the University of Kentucky Startup Fund. References [1] Dana Chuderland and Rony Seger. Protein-protein interactions in the regulation of the extracellular signal-regulated kinase. Mol. Biotechnol., 29:57–74, 2005. [2] Harry Jubb, Tom L Blundell, and David B Ascher. Flexibility and small pockets at protein–protein interfaces: new insights into druggability. Prog. Biophys. Mol., 119(1):2–9, 2015. [3] Mileidy W Gonzalez and Maricel G Kann. Chapter 4: Protein interactions and disease. PLoS Comput. Biol., 8(12):e1002819, 2012. [4] Cunliang Geng, Li C Xue, Jorge Roel-Touris, and Alexandre MJJ Bonvin. Finding the δδg spot: are predictors of binding affinity changes upon mutations in protein–protein interactions ready for it? Wiley Interdiscip. Rev. Comput. Mol. Sci., 9(5):e1410, 2019. [5] Rocco Moretti, Sarel J Fleishman, Rudi Agius, Mieczyslaw Torchala, Paul A Bates, Panagiotis L Kastritis, Joao PGLM Rodrigues, Mika¨el Trellet, Alexandre MJJ Bonvin, Meng Cui, et al. Community-wide evaluation of methods for predicting the effect of mutations on protein–protein interactions. Proteins: Struct. Funct. Genet., 81(11):1980–1987, 2013. [6] Jeffrey R Brender and Yang Zhang. Predicting the effect of mutations on protein-protein binding interactions through structure-based interface profiles. PLoS Comput. Biol., 11(10):e1004494, 2015. [7] Ning Zhang, Yuting Chen, Haoyu Lu, Feiyang Zhao, Roberto Vera Alvarez, Alexander Goncearenco, Anna R Panchenko, and Minghui Li. Mutabind2: predicting the impacts of single and multiple mutations on protein-protein interactions. Iscience, 23(3):100939, 2020. [8] Carlos HM Rodrigues, Yoochan Myung, Douglas EV Pires, and David B Ascher. mcsm-ppi2: predicting the effects of mutations on protein–protein interactions. Nucleic Acids Res., 47(W1):W338–W344, 2019. [9] Minghui Li, Marharyta Petukh, Emil Alexov, and Anna R Panchenko. Predicting the impact of missense mutations on protein–protein binding affinity. J. Chem. Theory Comput., 10(4):1770–1780, 2014. [10] Hafumi Nishi, Manoj Tyagi, Shaolei Teng, Benjamin A Shoemaker, Kosuke Hashimoto, Emil Alexov, Stefan Wuchty, and Anna R Panchenko. Cancer missense mutations alter binding properties of proteins and their interaction networks. PloS one, 8(6):e66273, 2013. [11] Mu Gao, Hongyi Zhou, and Jeffrey Skolnick. Insights into disease-associated mutations in the human proteome through protein structural analysis. Structure, 23(7):1362–1369, 2015. [12] Alessia David, Rozami Razali, Mark N Wass, and Michael JE Sternberg. Protein–protein interaction sites are hot spots for disease-associated nonsynonymous snps. Hum. Mutat., 33(2):359–363, 2012. [13] H Billur Engin, Jason F Kreisberg, and Hannah Carter. Structure-based analysis reveals cancer missense mutations target protein interaction interfaces. PLoS One, 11(4):e0152929, 2016. [14] Amelie Stein, Douglas M Fowler, Rasmus Hartmann-Petersen, and Kresten Lindorff-Larsen. Biophysical and mechanistic models for disease-causing protein variants. Trends Biochem. Sci., 44(7):575–588, 2019. [15] Stephanie Portelli, Jody E Phelan, David B Ascher, Taane G Clark, and Nicholas Furnham. Understanding molecular consequences of putative drug resistant mutations in mycobacterium tuberculosis. Sci. Rep., 8(1):1–12, 2018. [16] Sundeep Chaitanya Vedithi, Sony Malhotra, Madhusmita Das, Sheela Daniel, Nanda Kishore, Anuja George, Shantha Arumugam, Lakshmi Rajan, Mannam Ebenezer, David B Ascher, et al. Structural implications of mutations conferring rifampin resistance in mycobacterium leprae. Sci. Rep., 8(1):5016, 2018. [17] Vytautas Gapsys, Servaas Michielssens, Daniel Seeliger, and Bert L de Groot. Accurate and rigorous prediction of the changes in protein free energies in a large-scale mutation scan. Angew. Chem., Int. Ed., 55(26):7364–7368, 2016. [18] Elizabeth H Kellogg, Andrew Leaver-Fay, and David Baker. Role of conformational sampling in computing mutationinduced changes in protein structure and stability. Proteins: Structure, Function, and Bioinformatics, 79(3):830–838, 2011. [19] Brian J Bender, Alberto Cisneros III, Amanda M Duran, Jessica A Finn, Darwin Fu, Alyssa D Lokits, Benjamin K Mueller, Amandeep K Sangha, Marion F Sauer, Alexander M Sevy, et al. Protocols for molecular modeling with rosetta3 and rosettascripts. Biochemistry, 55(34):4748–4763, 2016. [20] Kurt S Thorn and Andrew A Bogan. Asedb: a database of alanine mutations and their effects on the free energy of binding in protein interactions. Bioinformatics, 17(3):284–285, 2001. [21] MD Shaji Kumar and M Michael Gromiha. Pint: protein–protein interactions thermodynamic database. Nucleic Acids Res., 34(suppl 1):D195–D198, 2006. [22] MD Shaji Kumar, K Abdulla Bava, M Michael Gromiha, Ponraj Prabakaran, Koji Kitajima, Hatsuho Uedaira, and Akinori Sarai. Protherm and pronit: thermodynamic databases for proteins and protein–nucleic acid interactions. Nucleic Acids Res., 34(suppl 1):D204–D206, 2006. [23] Iain H Moal and Juan Fern´andez-Recio. Skempi: a structural kinetic and energetic database of mutant protein interactions and its use in empirical models. Bioinformatics, 28(20):2600–2607, 2012. [24] Justina Jankauskait˙e, Brian Jim´enez-Garc´ıa, Justas Dapk¯unas, Juan Fern´andez-Recio, and Iain H Moal. Skempi 2.0: an updated benchmark of changes in protein–protein binding energy, kinetics and thermodynamics upon mutation. Bioinformatics, 35(3):462–469, 2019. [25] Sarah Sirin, James R Apgar, Eric M Bennett, and Amy E Keating. Ab-bind: antibody binding mutational database for computational affinity predictions. Protein Sci., 25(2):393–409, 2016. [26] Cunliang Geng, Anna Vangone, and Alexandre MJJ Bonvin. Exploring the interplay between experimental methods and the performance of predictors of binding affinity change upon mutations in protein complexes. Protein Eng. Des. Sel., 29(8):291–299, 2016. [27] Sherlyn Jemimah, K Yugandhar, and M Michael Gromiha. Proximate: a database of mutant protein–protein complex thermodynamics and kinetics. Bioinformatics, 33(17):2787–2788, 2017. [28] Douglas EV Pires, David B Ascher, and Tom L Blundell. mcsm: predicting the effects of mutations in proteins using graph-based signatures. Bioinformatics, 30(3):335–342, 2014. [29] Cunliang Geng, Anna Vangone, Gert E Folkers, Li C Xue, and Alexandre MJJ Bonvin. isee: Interface structure, evolution, and energy-based machine learning predictor of binding affinity changes upon mutations. Proteins: Structure, Function, and Bioinformatics, 87(2):110–119, 2019. [30] Sherlyn Jemimah, Masakazu Sekijima, and M Michael Gromiha. Proaffimuseq: sequence-based method to predict the binding free energy change of protein–protein complexes upon mutation using functional classification. Bioinformatics, 36(6):1725–1730, 2020. [31] Guangyu Zhou, Muhao Chen, Chelsea JT Ju, Zheng Wang, Jyun-Yu Jiang, and Wei Wang. Mutation effect estimation on protein–protein interactions using deep contextualized representation learning. NAR genom. bioinform., 2(2):lqaa015, 2020. [32] Alexey Strokach, Tian Yu Lu, and Philip M Kim. Elaspic2 (el2): combining contextualized language models and graph neural networks to predict effects of mutations. J. Mol. Biol., 433(11):166810, 2021. [33] Xianggen Liu, Yunan Luo, Pengyong Li, Sen Song, and Jian Peng. Deep geometric representations for modeling effects of mutations on protein-protein binding affinity. PLoS Comput. Biol., 17(8):e1009284, 2021. [34] Piero Fariselli, Pier Luigi Martelli, Castrense Savojardo, and Rita Casadio. Inps: predicting the impact of nonsynonymous variations on protein stability from sequence. Bioinformatics, 31(17):2816–2821, 2015. [35] Grant Thiltgen and Richard A Goldstein. Assessing predictors of changes in protein stability upon mutation using self-consistency. PLoS One, 7(10):e46084, 2012. [36] Fabrizio Pucci, Katrien V Bernaerts, Jean Marc Kwasigroch, and Marianne Rooman. Quantification of biases in predictions of protein stability changes upon mutations. Bioinformatics, 34(21):3659–3665, 2018. [37] Dinara R Usmanova, Natalya S Bogatyreva, Joan Ari˜no Bernad, Aleksandra A Eremina, Anastasiya A Gorshkova, German M Kanevskiy, Lyubov R Lonishin, Alexander V Meister, Alisa G Yakupova, Fyodor A Kondrashov, et al. Self-consistency test reveals systematic bias in programs for prediction change of stability upon mutation. Bioinformatics, 34(21):3653–3658, 2018. [38] Duc D Nguyen, Tian Xiao, Menglun Wang, and Guo-Wei Wei. Rigidity strengthening: A mechanism for protein– ligand binding. J. Chem. Inf. Model., 57(7):1715–1721, 2017. [39] Md Masud Rana and Duc Duy Nguyen. Geometric graph learning with extended atom-types features for proteinligand binding affinity prediction. Comput. Biol. Med., 164:107250, 2023. [40] Jian Jiang, Rui Wang, and Guo-Wei Wei. Ggl-tox: geometric graph learning for toxicity prediction. J. Chem. Inf. Model., 61(4):1691–1700, 2021. [41] Menglun Wang, Zixuan Cang, and Guo-Wei Wei. A topology-based network tree for the prediction of protein–protein binding affinity changes following mutation. Nat. Mach. Intell., 2(2):116–123, 2020. [42] Duan Chen, Zhan Chen, Changjun Chen, Weihua Geng, and Guo-Wei Wei. Mibpb: a software package for electrostatic analysis. J. Comput. Chem., 32(4):756–770, 2011. [43] Xiang Liu, Huitao Feng, Jie Wu, and Kelin Xia. Hom-complex-based machine learning (hcml) for the prediction of protein–protein binding affinity changes upon mutation. J. Chem. Inf. Model., 62(17):3961–3969, 2022. [44] Douglas EV Pires and David B Ascher. mcsm-ab: a web server for predicting antibody–antigen affinity changes upon mutation with graph-based signatures. Nucleic Acids Res., 44(W1):W469–W473, 2016. [45] Peng Xiong, Chengxin Zhang, Wei Zheng, and Yang Zhang. Bindprofx: assessing mutation-induced binding affinity change by protein interface profiles with pseudo-counts. J. Mol. Biol., 429(3):426–434, 2017. [46] Quanya Liu, Peng Chen, Bing Wang, Jun Zhang, and Jinyan Li. dbmpikt: a database of kinetic and thermodynamic mutant protein interactions. BMC bioinformatics, 19(1):1–7, 2018. [47] Bian Li, Yucheng T Yang, John A Capra, and Mark B Gerstein. Predicting changes in protein thermodynamic stability upon point mutation with deep 3d convolutional neural networks. PLoS Comp. Bio., 16(11):e1008291, 2020. [48] Lijun Quan, Qiang Lv, and Yang Zhang. Strum: structure-based prediction of protein stability changes upon single-point mutation. Bioinformatics, 32(19):2936–2946, 2016. [49] Leo Breiman. Random forests. Machine learning, 45:5–32, 2001. [50] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20:273–297, 1995. [51] Duc Duy Nguyen, Kaifu Gao, Menglun Wang, and Guo-Wei Wei. Mathdl: mathematical deep learning for d3r grand challenge 4. J. Comput. Aided. Mol. Des., 34(2):131–147, 2020. [52] Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pages 1189–1232, 2001. This paper is available on under CC 4.0 license. Arxiv

PPIs and the Prediction of Mutation-Induced Binding Free Energy Changes: What It All Means

This paper is available on arxiv under CC 4.0 license. Authors: (1) Md Masud Rana, Department of Mathematics, University of Kentucky; (2) Duc Duy Nguyen, Department of Mathematics, University of Kentucky & ducnguyen@uky.edu. Table of Links Abstract & Introduction Datasets and Results Methods Conclusion, Data and Software Availability, Competing interests, Acknowledgments & References 3 Methods 3.1 Graph Theory and Atom-level Interactions in Biomolecules Graph theory provides a mathematical framework that is widely applied in the study of biomolecules such as proteins, DNA, and RNA. For a biomolecule, a graph G(V, E) is a collection of nodes V and edges E that can represent the connectivity and relationships between different atoms or residues within the molecule. A refinement to this representation is graph coloring, a technique that assigns unique labels to different atom types within the biomolecule. This enriched, colored graph encodes diverse atomic interactions, paving the way for a collective and coarse-grained description of the dataset. In this representation, atoms with assigned labels are organized into subgraphs, and the colored edges between them represent atom-specific interactions. The advantage of using subgraphs lies in their ability to focus on specific regions or components of the biomolecule. By isolating relevant subsets of atoms, subgraphs allow us to identify localized patterns, interactions, or clusters that might not be evident in the global graph representation. This targeted approach provides a more nuanced understanding of the structural and functional properties of biomolecules. To extract atom-level interaction information, we consider specific atom types based on their names in the PDB structure such as carbon alpha (CA), carbon beta (CB), carbon delta-1 (CD1), etc. These atom names serve as identifiers for specific positions within a protein’s three-dimensional structure. They help define the individual atoms that constitute amino acids, the building blocks of proteins, and provide crucial information about their spatial orientation and chemical properties. We consider a total of 37 distinct atom names that are frequently found in protein structures within the PDB database. These atom types are represented by the set A. To simplify the notation, we assume the set A is sorted in alphanumeric order, A = {C, CA, CB, · · · , N, ND1, ND2, · · · , O, OD1, · · · , SD, SG}, serves as a measure of the combined strength of interaction between chosen pairs of atom types, providing valuable insights into the molecular structure and properties. 3.2 Geometric Subgraph Representation of PPIs In the context of studying protein-protein interactions (PPIs) and predicting the effects of mutations on these interactions, it is important to focus on the relevant regions where the interactions occur. While protein-protein complexes can consist of a large number of atoms, the interactions between proteins primarily take place at specific regions known as interfaces. To streamline computational costs and concentrate on pertinent information, it is common practice to consider only the protein atoms near the binding sites. The binding site, in this context, refers to the region within a certain cutoff distance c from the chain where the mutation occurred. By defining the binding site in this way, we can narrow our focus to the specific area where the interaction and subsequent effects of the mutation are most pronounced. Furthermore, when analyzing the effects of mutations, it is crucial to incorporate geometric graph information from the mutation sites and their neighboring regions. The mutation site is defined as the region within a cutoff distance c from the mutated residue, allowing us to capture the structural changes resulting from the mutation. To construct a site-specific multiscale weighted colored geometric subgraph (MWCGS) representation for a PPI, both the wild-type and mutant-type proteins are considered. This leads to four sets of features for each PPI, corresponding to the two sites and the two types of proteins involved. Each set consists of 37 × 37 = 1369 MWCGS features, representing the interactions between the atom types involved in the PPI. These features encompass diverse chemical and biological properties, such as the presence of specific interatomic interactions involving oxygen and nitrogen atoms, the hydrophobic nature of certain regions, and the ability of atoms to undergo polarization, among other relevant molecular characteristics. By utilizing these site-specific MWCGS features, we can uncover valuable insights into the effects of mutations and the underlying molecular interactions, revealing significant information and characteristics embedded within the PPI system. 3.3 Geometric Graph Learning for PPIs Accurately predicting the changes in binding affinity induced by mutations in protein-protein complexes poses a significant challenge due to the complex nature of these systems. The interactions between proteins are highly intricate, and the effects of mutations can be subtle and context-dependent. Machine learning techniques offer a promising approach to tackle this problem by leveraging the power of data-driven models to capture complex patterns and relationships. Machine learning algorithms can aid in predicting mutation-induced binding affinity changes by learning from a set of training examples that consist of protein-protein complexes with known experimental binding affinities. These algorithms can analyze the features extracted from the complexes, such as geometric graph information, to identify relevant patterns and associations between the features and the binding affinities. By learning from these patterns, the algorithms can generalize and make predictions on unseen protein-protein complexes. There are several machine learning algorithms that can be used in combination with geometric graph features to predict binding affinity changes. These algorithms include random forests [49], support vector machines (SVM) [50], neural networks [51], and gradient boosting trees (GBT) [52]. Each algorithm has its strengths and weaknesses, and their performance can vary depending on the specific problem and dataset. Among these algorithms, gradient boosting trees (GBT) have gained significant popularity in recent years [39]. GBT is an ensemble method that builds a sequence of weak learners, typically decision trees, to correct the errors made by the previous learners. By combining these weak learners, GBT can effectively model complex relationships and improve prediction accuracy. One advantage of GBT is its robustness against overfitting, which is especially beneficial when dealing with a moderate number of features. Additionally, GBT models can provide interpretability, allowing us to gain insights into the factors contributing to the binding affinity changes. The implementation of the GBT algorithm in this study utilized the scikit-learn package (v 0.24.1). To optimize the performance of the GBT model for ensemble methods, specific hyperparameters were fine-tuned. The number of estimators was set to 40000, indicating the number of weak learners in the ensemble, while the learning rate was set to 0.001, determining the contribution of each weak learner to the final prediction. Given the large number of features involved in the prediction task, an efficient training process was achieved by limiting the maximum number of features considered to the square root of the descriptor length. This approach helped expedite the training process without compromising the overall performance of the GBT model. To ensure reliable performance evaluation, fifty runs were performed for each feature set, employing different random seeds. By averaging the results obtained from these runs, a more robust and representative performance measure was obtained. Despite the complexity of the prediction task and the involvement of numerous features, the selected parameter settings and multiple runs yielded satisfactory performance results. The GBT approach was chosen for its ability to effectively handle overfitting, exhibit good performance with moderately sized datasets, and provide interpretable models. These characteristics make GBT a suitable and reliable choice for this study, enabling accurate predictions of mutation-induced binding affinity changes in protein-protein complexes using the provided geometric graph features. This paper is available on under CC 4.0 license. Arxiv

The Methods We Used to Predict Mutation-Induced Binding Free Energy Changes

This paper is available on arxiv under CC 4.0 license. Authors: (1) Md Masud Rana, Department of Mathematics, University of Kentucky; (2) Duc Duy Nguyen, Department of Mathematics, University of Kentucky & ducnguyen@uky.edu. Table of Links Abstract & Introduction Datasets and Results Methods Conclusion, Data and Software Availability, Competing interests, Acknowledgments & References Abstract Protein-protein interactions (PPIs) are critical for various biological processes, and understanding their dynamics is essential for decoding molecular mechanisms and advancing fields such as cancer research and drug discovery. Mutations in PPIs can disrupt protein binding affinity and lead to functional changes and disease. Predicting the impact of mutations on binding affinity is valuable but experimentally challenging. Computational methods, including physics-based and machine learning-based approaches, have been developed to address this challenge. Machine learning-based methods, fueled by extensive PPI datasets such as Ab-Bind, PINT, SKEMPI, and others, have shown promise in predicting binding affinity changes. However, accurate predictions and generalization of these models across different datasets remain challenging. Geometric graph learning has emerged as a powerful approach, combining graph theory and machine learning, to capture structural features of biomolecules. We present GGL-PPI, a novel method that integrates geometric graph learning and machine learning to predict mutation-induced binding free energy changes. GGL-PPI leverages atom-level graph coloring and multi-scale weighted colored geometric subgraphs to extract informative features, demonstrating superior performance on three validation datasets, namely AB-Bind, SKEMPI 1.0, and SKEMPI 2.0 datasets. Evaluation on a blind test set highlights the unbiased predictions of GGLPPI for both direct and reverse mutations. The findings underscore the potential of GGL-PPI in accurately predicting binding free energy changes, contributing to our understanding of PPIs and aiding drug design efforts. — geometric graph, machine learning, protein-protein interactions, mutation, binding free energy changes Keywords 1 Introduction Protein-protein interactions (PPIs) play a fundamental role in numerous biological processes, including cell signaling, metabolic pathways, and immune responses [1;2;3]. Understanding PPIs and their dynamics is crucial for unraveling the intricate mechanisms underlying these processes and holds significant implications for various fields, such as cancer research, drug discovery, and personalized medicine [3;4]. The effects of mutations on PPIs have drawn substantial attention due to their potential impact on protein function and cellular behavior [5;6;7;8]. Missense mutations, which involve single amino acid substitutions, can disrupt the binding affinity between proteins and their partners [9;10]. Such alterations can lead to malfunctioning PPI networks, resulting in diseases, drug resistance, or other molecular disorders [11;12;13;14;15;16]. Therefore, accurate prediction of the impact of mutations on binding affinity holds significant importance in understanding disease mechanisms, facilitating therapeutic interventions, and enabling the design of innovative biopharmaceuticals. One of the key parameters used to assess the impact of mutations on PPIs is the binding free energy change (∆∆G). This thermodynamic parameter quantifies the difference in binding affinity between the wild-type and mutant protein complexes. Experimental determination of ∆∆G values, while accurate, can be tedious and costly. Consequently, there has been a surge in the development of computational methods to predict these energy changes. Broadly, these computation approaches fall into two main categories: physics-based and machine learning-based methods. The former, rooted in biophysical principles, delves into protein conformations and offers a rigorous approach [17;18;19]. However, they often demand significant computational resources and are not always scalable. On the other hand, machine learning-based methods have gained popularity due to their scalability and rapid prediction capabilities. Leveraging the wealth of data from PPI datasets such as ASEdb [20], PINT[21], ProTherm[22], SKEMPI [23;24], and others [25;26;27], machine learning models like mCSM28, BindProf 6 , iSEE29, MutaBind [7] , and several others [30;31;32;33] have been developed. These models have shown significant potential in predicting ∆∆Gs. However, challenges such as imbalanced training datasets, generalization across different PPI datasets, and the intricacy of capturing complex sequence-structure-function relationships remain obstacles [34;35;36;37]. This underscores the need for further research to enhance machine learning methodologies, ensuring accurate and efficient ∆∆G predictions. In recent years, geometric graph learning has emerged as a promising approach for analyzing complex biomolecular systems [38;39;40]. By representing proteins and their interactions as graphs, this methodology leverages the power of graph theory and machine learning to capture essential structural and spatial features of the biomolecular complexes. Specifically, the use of geometric subgraphs, which encode local interactions between atoms and residues, offers a rich representation. This not only sheds light on intricate molecular details but also provides insights into their impact on binding affinity [39]. This work presents a novel method, called GGL-PPI (Geometric Graph Learning for Protein-Protein Interactions), which combines the principles of geometric graph learning and machine learning to predict mutation-induced binding free energy changes. The workflow of GGL-PPI is depicted in Figure 1. Central to its methodology, GGL-PPI utilizes atom-level graph coloring and multi-scale weighted colored geometric subgraphs, enabling the extraction of informative features from protein structures and their interactions. These features serve as inputs to a gradient-boosting tree model, which facilitates precise and consistent predictions of binding free energy change upon mutations. When compared with existing models, GGL-PPI consistently outperforms state-of-the-art approaches across all datasets. Further addressing its generalizability, GGL-PPI was evaluated on a blind test set, Ssym dataset [36]. This evaluation was conducted using a homology-reduced balanced training set to avert data leakage, showcasing GGL-PPI’s robust performance and ability to produce unbiased predictions for both direct and reverse mutations. This paper is available on under CC 4.0 license. Arxiv

GGL-PPI: Geometric Graph Learning to Predict Mutation-Induced Binding Free Energy Changes

This paper is available on arxiv under CC 4.0 license. Authors: (1) Matu´s Medo, Department for BioMedical Research, Inselspital, Bern University Hospital, University of Bern, Department of Radiation Oncology, Inselspital, Bern University Hospital, University of Bern and matus.medo@unifr.ch; (2)  Michaela Medova, Department for BioMedical Research, Inselspital, Bern University Hospital, University of Bern, and Department of Radiation Oncology, Inselspital, Bern University Hospital, University of Bern. Table of Links Abstract & Introduction Results Discussion Materials and methods Acknowledgement & References Supporting Information Supporting Information This paper is available on under CC 4.0 license. Arxiv

Extra Information on the Comprehensive Comparison of Tools for Fitting Mutational Signatures

This paper is available on arxiv under CC 4.0 license. Authors: (1) Matu´s Medo, Department for BioMedical Research, Inselspital, Bern University Hospital, University of Bern, Department of Radiation Oncology, Inselspital, Bern University Hospital, University of Bern and matus.medo@unifr.ch; (2)  Michaela Medova, Department for BioMedical Research, Inselspital, Bern University Hospital, University of Bern, and Department of Radiation Oncology, Inselspital, Bern University Hospital, University of Bern. Table of Links Abstract & Introduction Results Discussion Materials and methods Acknowledgement & References Supporting Information Acknowledgement We thank Charlotte Ng and Peter Degen for their useful feedback. References Alexandrov, L.B., Kim, J., Haradhvala, N.J., Huang, M.N., Tian Ng, A.W., Wu, Y., Boot, A., Covington, K.R., Gordenin, D.A., Bergstrom, E.N., et al., 2020. The repertoire of mutational signatures in human cancer. Nature 578, 94–101. Alexandrov, L.B., Nik-Zainal, S., Wedge, D.C., Aparicio, S.A., Behjati, S., Biankin, A.V., Bignell, G.R., Bolli, N., Borg, A., Børresen-Dale, A.L., et al., 2013. Signatures of mutational processes in human cancer. Nature 500, 415–421. Berger, B., Yu, Y.W., 2022. Navigating bottlenecks and trade-offs in genomic data analysis. Nature Reviews Genetics , 1–16. Blokzijl, F., Janssen, R., van Boxtel, R., Cuppen, E., 2018. MutationalPatterns: Comprehensive genome-wide analysis of mutational processes. Genome Medicine 10, 1–11. Brady, S.W., Gout, A.M., Zhang, J., 2022. Therapeutic and prognostic insights from the analysis of cancer mutational signatures. Trends in Genetics 38, 194–208. Cannataro, V.L., Mandell, J.D., Townsend, J.P., 2022. Attribution of cancer origins to endogenous, exogenous, and preventable mutational processes. Molecular Biology and Evolution 39, msac084. Degasperi, A., Zou, X., Dias Amarante, T., Martinez-Martinez, A., Koh, G.C.C., Dias, J.M., Heskin, L., Chmelova, L., Rinaldi, G., Wang, V.Y.W., et al., 2022. Substitution mutational signatures in whole-genome–sequenced cancers in the UK population. Science 376, abl9283. Diaz-Gay, M., Vangara, R., Barnes, M., Wang, X., Islam, S.A., Vermes, I., Narasimman, N.B., Yang, T., Jiang, Z., Moody, S., et al., 2023. Assigning mutational signatures to individual samples and individual somatic mutations with SigProfilerAssignment. bioRxiv , 548264doi:10. 1101/2023.07.10.548264. bioRxiv 2023.07.10.548264. Gori, K., Baez-Ortega, A., 2020. sigfit: Flexible Bayesian inference of mutational signatures. bioRxiv , 372896doi:10.1101/372896. bioRxiv, 372896. Gulhan, D.C., Lee, J.J.K., Melloni, G.E., Cortes-Ciriano, I., Park, P.J., 2019. Detecting the mutational signature of homologous recombination deficiency in clinical samples. Nature Genetics 51, 912–919. Hubschmann, D., Jopp-Saile, L., Andresen, C., Kr ¨ amer, S., Gu, Z., Heilig, C.E., Kreutzfeldt, S., Teleanu, V., Fr ¨ ohling, S., Eils, R., et al., 2021. ¨ Analysis of mutational signatures with yet another package for signature analysis. Genes, Chromosomes and Cancer 60, 314–331. Islam, S.A., D´ıaz-Gay, M., Wu, Y., Barnes, M., Vangara, R., Bergstrom, E.N., He, Y., Vella, M., Wang, J., Teague, J.W., et al., 2022. Uncovering novel mutational signatures by de novo extraction with SigProfilerExtractor. Cell Genomics 2, 100179. Kim, Y.A., Leiserson, M.D., Moorjani, P., Sharan, R., Wojtowicz, D., Przytycka, T.M., 2021. Mutational signatures: From methods to mechanisms. Annual Review of Biomedical Data Science 4, 189–206. Koh, G., Degasperi, A., Zou, X., Momen, S., Nik-Zainal, S., 2021. Mutational signatures: Emerging concepts, caveats and clinical applications. Nature Reviews Cancer 21, 619–637. Li, S., 2020. sigLASSO: Optimizing cancer mutation signatures jointly with sampling likelihood. URL: https://github.com/gersteinlab/ siglasso. R package version 1.1. Li, S., Crawford, F.W., Gerstein, M.B., 2020. Using sigLASSO to optimize cancer mutation signatures jointly with sampling likelihood. Nature Communications 11, 3575. Maura, F., Degasperi, A., Nadeu, F., Leongamornlert, D., Davies, H., Moore, L., Royo, R., Ziccheddu, B., Puente, X.S., Avet-Loiseau, H., Campbell, P.J., Nik-Zainal, S., Campo, E., Munshi, N., Bolli, N., 2019. A practical guide for mutational signature analysis in hematological malignancies. Nature Communications 10, 1–12. Missa, O., Dytham, C., Morlon, H., 2016. Understanding how biodiversity unfolds through time under neutral theory. Philosophical Transactions of the Royal Society B: Biological Sciences 371, 20150226. Nik-Zainal, S., Alexandrov, L.B., Wedge, D.C., Van Loo, P., Greenman, C.D., Raine, K., Jones, D., Hinton, J., Marshall, J., Stebbings, L.A., et al., 2012. Mutational processes molding the genomes of 21 breast cancers. Cell 149, 979–993. Nik-Zainal, S., Davies, H., Staaf, J., Ramakrishna, M., Glodzik, D., Zou, X., Martincorena, I., Alexandrov, L.B., Martin, S., Wedge, D.C., et al., 2016. Landscape of somatic mutations in 560 breast cancer whole-genome sequences. Nature 534, 47–54. Omichessan, H., Severi, G., Perduca, V., 2019. Computational tools to detect signatures of mutational processes in DNA from tumours: A review and empirical comparison of performance. PLoS ONE 14, e0221235. Pandey, P., Arora, S., Rosen, G.L., 2022. MetaMutationalSigs: Comparison of mutational signature refitting results made easy. Bioinformatics 38, 2344–2347. Riva, L., Pandiri, A.R., Li, Y.R., Droop, A., Hewinson, J., Quail, M.A., Iyer, V., Shepherd, R., Herbert, R.A., Campbell, P.J., et al., 2020. The mutational signature profile of known and suspected human carcinogens in mice. Nature Genetics 52, 1189–1197. Rosenthal, R., McGranahan, N., Herrero, J., Taylor, B.S., Swanton, C., 2016. DeconstructSigs: Delineating mutational processes in single tumors distinguishes DNA repair deficiencies and patterns of carcinoma evolution. Genome Biology 17, 1–11. Rustad, E.H., Nadeu, F., Angelopoulos, N., Ziccheddu, B., Bolli, N., Puente, X.S., Campo, E., Landgren, O., Maura, F., 2021. mmsig: A fitting approach to accurately identify somatic mutational signatures in hematological malignancies. Communications Biology 4, 1–12. Schumann, F., Blanc, E., Messerschmidt, C., Blankenstein, T., Busse, A., Beule, D., 2019. SigsPack, A package for cancer mutational signatures. BMC Bioinformatics 20, 1–9. Van Hoeck, A., Tjoonk, N.H., van Boxtel, R., Cuppen, E., 2019. Portrait of a cancer: Mutational signature analyses for cancer diagnostics. BMC Cancer 19, 1–14. Wang, S., Li, H., Song, M., Tao, Z., Wu, T., He, Z., Zhao, X., Wu, K., Liu, X.S., 2021. Copy number signature analysis tool and its application in prostate cancer reveals distinct mutational processes and clinical outcomes. PLoS Genetics 17, e1009557. Wu, Y., Chua, E.H.Z., Ng, A.W.T., Boot, A., Rozen, S.G., 2022. Accuracy of mutational signature software on correlated signatures. Scientific Reports 12, 1–12. This paper is available on under CC 4.0 license. Arxiv

The People We Have to Thank In Our Comparison of Tools for Fitting Mutational Signatures

This paper is available on arxiv under CC 4.0 license. Authors: (1) Matu´s Medo, Department for BioMedical Research, Inselspital, Bern University Hospital, University of Bern, Department of Radiation Oncology, Inselspital, Bern University Hospital, University of Bern and matus.medo@unifr.ch; (2)  Michaela Medova, Department for BioMedical Research, Inselspital, Bern University Hospital, University of Bern, and Department of Radiation Oncology, Inselspital, Bern University Hospital, University of Bern. Table of Links Abstract & Introduction Results Discussion Materials and methods Acknowledgement & References Supporting Information 4. Materials and methods 4.1. Reference signatures We used all signatures from version 3.0 of the COSMIC catalog (COSMICv3, https://cancer.sanger.ac. uk/signatures/sbs/), in particular the SBS signatures for human genome assembly GRCh38. COSMICv3 contains 67 mutational signatures (18 are artifact signatures) defined in 96 mutational contexts. While newer COSMIC versions (the latest version is 3.3.1 from June 2022) added more signatures, profiles of the COSMICv3 signatures have not been altered (all absolute weight differences are below 10−7 ). To measure the diversity of signature profiles, we compute their exponentiated Shannon index which is a common measure of diversity (Missa et al., 2016) that can be understood as the effective number of active mutational contexts. For a signature whose all weight is concentrated in one context, the exponentiated Shannon index is one. For a signature with the same weight 1/96 of all contexts, the exponentiated Shannon index is 96. For COSMICv3 signatures, the exponentiated Shannon index ranges from 2.7 (SBS48) to 80.3 (SBS3). 4.2. Synthetic mutational catalogs Absolute contributions of signatures to sequenced tissues from various cancer types were downloaded from the Catalogue Of Somatic Mutations In Cancer (COSMIC, https://cancer.sanger.ac.uk/signatures/sbs/, catalog version 3.2) on November 14, 2021 for all 46 non-artifact SBS signatures that have tissue contribution data available. These data included only samples with reconstruction accuracy above 0.90 and at least 10 mutations attributed to the specific SBS signature. Using the provided unique sample identifiers, we used these files to compute the relative signature contributions in individual WGS-sequenced samples that are stratified by the cancer type. We chose eight different cancer types for further analysis: Hepatocellular carcinoma (Liver-HCC, n = 422), stomach adenocarcinoma (Stomach-AdenoCA, n = 170), head and neck squamous cell carcinoma (Head-SCC, n = 57), colorectal carcinoma (ColoRect-AdenoCA, n = 72), lung adenocarcinoma (Lung-AdenoCA, n = 62), cutaneous melanoma (Skin-Melanoma, n = 280), non-Hodgkin Lymphoma (Lymph-BNHL, n = 117), and glioblastoma (CNS-GBM, n = 63). The approach described above allows us to reproduce empirical signature weights in previously analyzed samples without resorting to assumptions such as a log-normal distribution of the number of mutations due to a given signature (Alexandrov et al., 2020, Islam et al., 2022) or adding additional zeros to the Poisson distribution to reproduce signatures that are not active in a sample (Omichessan et al., 2019). The code for generating synthetic mutational catalogs and evaluating the signature fitting tools is available at https://github.com/8medom/SigFitTest. For Figure 6, we created synthetic mutational catalogs with a systematic difference in the activity of signature SBS40. After generating sample weights as described in the previous paragraph (assuming the CNS-GBM cancer type), the relative weights of SBS40 were multiplied by 1.3 in the first half of the samples and divided by 1.3 in the second half of the samples. The relative weights of all signatures in each sample were then normalized to one. Note that signature SBS40 is active in nearly all CNS-GBM samples (Fig. SF9 in SI) and its median relative weight is close to 50%. By the described process, the median weights in the two groups of samples become 42% and 55%, respectively. 4.3. Tools for signature fitting The task of fitting known mutational signatures to a mutational catalog consists of finding the combination of signatures from a reference set that “best” matches the given catalog. Denoting the matrix with reference signatures as S, where S cs is the relative weight of context c for signature s, and the given normalized mutational catalog as m, where mci is the fraction of mutations in context c in sample i, this amounts to solving where wsi is the relative weight of signature s in sample i. Mathematically, this is an over-determined system as the number of reference signatures is smaller than the number of mutational contexts (96 contexts for the common SBS signatures). Several fitting tools are therefore based on minimizing the difference between m and Sw through nonnegative least squares (as the signature weights cannot be negative) or quadratic programming. We evaluated several tools that belong to this class: MutationalPatterns v3.4.1 (Blokzijl et al., 2018), YAPSA v1.20.1 (Hubschmann et al. ¨ , 2021), SigsPack v1.8.0 (Schumann et al., 2019), and sigminer v2.2.0 (Wang et al., 2021) which has three separate methods based on quadratic programming, non-linear least squares, and simulated annealing. We find that all these tools produce similar results. Other tools use various iterative processes by which the provided set of reference signatures is gradually reduced by removing the signatures, for example, whose inclusion does not considerably improve the match between the observed and reconstructed mutational catalogs (or, opposite, signatures are gradually added as long as the reconstruction accuracy sufficiently improves). We evaluated deconstructSigs v1.8.0 (Rosenthal et al., 2016), SigProfilerSingleSample v0.0.0.27 (Alexandrov et al., 2020), SigProfilerAssignment v0.0.30 (Diaz-Gay et al., 2023), mmsig v0.0.0.9000 (Rustad et al., 2021), and signature.tools.lib v2.2.0 (Degasperi et al., 2022), that all belong to this category. The newest tool, SigProfilerAssignment, combines backward and forward iterative adjustment of the reference catalog and these steps are repeated until convergence. Finally, SigLASSO v1.1 combines the data likelihood in a generative model with L1 regularization and prior knowledge (Li, 2020, Li et al., 2020). To allow for a fair comparison with other tools, we did not use prior knowledge when evaluating sigLASSO. In our experience, this tool sometimes fails to halt but starting it again with the same input data resolves the issue. A similar Bayesian framework is used by sigfit v2.2 (Gori and Baez-Ortega, 2020). The authors of sigfit recommend setting all signatures whose lower bounds of the estimated 95% confidence intervals are below 0.01 to zero. The authors of deconstructSigs recommend setting all signatures whose relative weights are below 0.06 to zero. All results shown for sigfit and deconstructSigs follow these recommendations. 4.4. Trimming reference signatures It has been argued that the removal of irrelevant reference signatures can improve the fitting results (Kim et al., 2021). To assess this hypothesis, we use a two-step process where: (1) We fit signatures using all COSMICv3 signatures as a reference and (2) keep only the signatures whose relative weight exceeds threshold w0 for at least 5 samples in our cohorts with 100 samples. We use thresholds w0 = 0.05 (m = 100), w0 = 0.03 (m = 2, 000) and w0 = 0.01 (m = 50, 000) which correspond to absolute signature contributions 5, 60, and 500, respectively. This pruning of reference signatures is beneficial when the number of mutations per sample is small (see m = 100 in Fig. S17 in SI). However, the converse is true when the number of mutations per sample is high, in particular for tools that perform well with COSMICv3 as a reference (m = 50, 000 in Fig. S17 in SI). To overcome this problem, we have also tested a less strict pruning where we keep all signatures whose relative weight exceeds w0 for at least one sample (see Fig. S18 in SI for the results). We have also tested the approach based on de novo extraction of signatures as suggested in (Maura et al., 2019). For signature extraction, we used SignatureAnalyzed v0.0.7 (https://github.com/getzlab/SignatureAnalyzer) with L1 prior on both W and H and a Poisson objective function for optimization. As recommended in (Maura et al., 2019), each extracted signature was then compared with individual signatures from COSMICv3 as well as linear combinations of two signatures from COSMICv3. The signature (or a pair of signatures) that yielded the smallest cosine distance was then added to the list of trimmed reference signatures for the given input data. When the number of mutations is small (m = 100), less than five signatures are selected, on average. When the number of mutations is large (m = 50, 000), 89% of the active signatures are selected, on average. A comparison of the results obtained by the two reference-trimming schemes is shown in Fig. S19 in SI. 4.5. Evaluation metrics Recent literature often classifies fitting results as true positives, false positives, true negatives, and false negatives, which allows computing evaluation metrics such as precision and specificity Omichessan et al. (2019), Islam et al. (2022), Diaz-Gay et al. (2023). We use instead quantitative metrics that measure the differences between the true relative signature weights (which are used to generate the input mutational catalogs) and the estimated relative signature weights. For tools that estimate absolute signature weights, those are first normalized by the number of mutations in each sample. and average it over all samples in the cohort to obtain fitting error. The lowest fitting error, 0, is achieved when the estimated signature weights are exact for all signatures and all samples. The highest fitting error, 1, is achieved when the estimated signature weights sum to one for each sample but they are all false positives. For example, when a sample has 40% contribution of SBS1 and 60% of SBS4 but a tool estimates 20% contribution of SBS2 and 80% contribution of SBS3, the fitting error is 1. There are some tools whose signature weight estimates do not sum up to one for each sample, typically as a result of the uncertainty implied by a small number of mutations in samples. The fitting error of those tools can be inflated due to these tools’ conservativeness. However, we probed whether additionally normalizing the estimated weights to one improves the fitting error achieved by those tools and found that this is not the case. We can thus conclude that these tools are not disfavored by measuring their fitting error. Another way to quantify the agreement between the true and estimated signature weights is by computing their Pearson correlation. For each sample where at least three signatures had positive either true or estimated weights, we computed the Pearson correlation coefficient between these two weight vectors whilst excluding all signatures that are zero for both of them. The obtained values were then averaged over all samples in the cohort. We finally computed false positive weight which quantifies how much weight is assigned to the signatures that are not active in a given sample, and then this quantity is averaged over all samples. This quantity too ranges from 0 (when no weight is assigned to inactive signatures) to 1 (when all weight is assigned to inactive signatures). This paper is available on under CC 4.0 license. arxiv

The Materials and Methods That We Used to Compare Tools for Fitting Mutational Signatures

This paper is available on arxiv under CC 4.0 license. Authors: (1) Matu´s Medo, Department for BioMedical Research, Inselspital, Bern University Hospital, University of Bern, Department of Radiation Oncology, Inselspital, Bern University Hospital, University of Bern and matus.medo@unifr.ch; (2)  Michaela Medova, Department for BioMedical Research, Inselspital, Bern University Hospital, University of Bern, and Department of Radiation Oncology, Inselspital, Bern University Hospital, University of Bern. Table of Links Abstract & Introduction Results Discussion Materials and methods Acknowledgement & References Supporting Information 3. Discussion The broad range of tools for fitting mutational signatures makes it difficult to understand which tool to choose for a given project. In this work, we provide a comprehensive assessment of eleven different tools on synthetic mutational catalogs. Using mutational catalogs where only one signature is active allows us to quantify the differences in the fitting difficulty of individual signatures. We find that flat signatures whose average similarity with other signatures is high are the most difficult to fit. To assess fitting tools, we use synthetic mutational catalogs whose signature activities are modeled based on eight distinct cancer types. We find that when the number of mutations is small (100 mutations per sample), SigProfilerSingleSample is the best tool to use for all cancer types. As the number of mutations increases, SigProfilerAssignment becomes the best tool for all cancer types with mmsig best for some cancer types for an intermediate number of mutations (2,000 mutations per sample). The results change little when Pearson correlation is used instead of fitting error for the evaluation (Figs. S22 and S23 in SI). The risk of overfitting the data by including too many signatures in the reference catalog is often discussed in the literature (Maura et al., 2019, Koh et al., 2021, Degasperi et al., 2022). We show that three methods (SigProfilerSingleSample, SigProfilerExtractor, and mmsig) are robust to such overfitting when the number of mutations per sample is not too small (Figs. S12 and S13 in SI). Crucially, we find that the common practice of excluding signatures from the reference catalog because they do not seem to be active (or are little active) in the analyzed data is little effective or even harmful, unless the number of mutations per sample is small (Fig. S16 in SI). In most cases it is preferable to let the built-in statistical methods of these tools to decide using the complete COSMIC catalog as a reference. While our work gives clear recommendations on which tools to consider and which to avoid, many issues can be addressed in the future to further improve the fitting of mutational signatures. First, a similar assessment of fitting tools can be done for other types of signatures: doublet base substitutions, small insertions and deletions, and copy number variations. Then, some tools (e.g., sigfit and mmsig) can compute confidence intervals for their estimates. For sigfit, we used these estimates in the way recommended by the authors: When the lower bound of the confidence interval for the relative signature weight is below 0.01, the signature is marked as absent in the sample (its relative weight is set to zero). Our results show that this recommended practice indeed improves the results achieved by sigfit. By bootstrapping (resampling the original mutational catalogs with replacement), confidence intervals could be computed also for the tools that do not compute them by themselves. It would be worth investigating whether thus-determined confidence intervals could also improve the performance of other fitting tools. To fit mutational signatures, it is commonly required that each sample has at least 50 (Riva et al., 2020) or 200 (Blokzijl et al., 2018) single base substitutions. However, different signatures are differently difficult to fit (Figure 1), so it is unlikely that such a universal threshold is meaningful. Based on the simulation framework established here, it would be possible to study the minimum necessary number of mutations for different signatures of interest and different cancer types. To best match the needs of practitioners, it would be possible to extend the simulation framework so that it finds the best-performing fitting tool for a given cancer type, a list of signatures of interest, and a given distribution of sample mutation counts. When an active signature is missing from the reference catalog because it is new or is falsely deemed inactive in a given set of samples, most fitting tools cannot cope with this situation and distribute all (or nearly all) mutations among signatures from the reference set (Fig. S15 in SI). Three tools do not suffer from this drawback—deconstructSigs, signature.tools.lib, and sigfit—but their performance is generally weak. One could aim to enhance one of the bestperforming tools, such as SigProfilerAssignment, with an additional step that would quantify whether given signatures are indeed likely to produce given mutational catalogs. Another approach to this problem is offered in (Maura et al., 2019) where the authors suggest a multistep process to simultaneously avoid under- and over-fitting. Mutational signatures are first extracted de novo, then they are assigned to existing signatures from a reference catalog, and thusdetermined active signatures are finally used to fit the original input data. While there are well-defined statistical principles for the first and third steps of this process, the second assignment step is largely ad hoc. A more principled approach could improve the outcome. More generally, COSMIC signatures are the result of analyzing tumor tissues from many different organs, so they can be viewed as an average across them (Degasperi et al., 2022). It might be more appropriate to construct organ-specific reference catalogs that would better reflect mutational processes that occur in these biologically diverse systems. The fast-growing number of sequenced samples would make such an effort possible. This paper is available on under CC 4.0 license. Arxiv

Discussing Tools for Fitting Mutational Signatures: A Comprehensive Comparison

Comparing Tools for Fitting Mutational Signatures: The Results of Our Work

This paper is available on arxiv under CC 4.0 license. Authors: (1) Matu´s Medo, Department for BioMedical Research, Inselspital, Bern University Hospital, University of Bern, Department of Radiation Oncology, Inselspital, Bern University Hospital, University of Bern and matus.medo@unifr.ch; (2)  Michaela Medova, Department for BioMedical Research, Inselspital, Bern University Hospital, University of Bern, and Department of Radiation Oncology, Inselspital, Bern University Hospital, University of Bern. Table of Links Abstract & Introduction Results Discussion Materials and methods Acknowledgement & References Supporting Information Abstract Mutational signatures connect characteristic mutational patterns in the genome with biological processes that take place in the tumor tissues. Analysis of mutational signatures can help elucidate tumor evolution, prognosis, and therapeutic strategies. Although tools for extracting mutational signatures de novo have been extensively benchmarked, a similar effort is lacking for tools that fit known mutational signatures to a given catalog of mutations. We fill this gap by comprehensively evaluating eleven signature fitting tools (well-established as well as recent) on synthetic input data. To create realistic input data, we use empirical signature weights in tumor tissue samples from the COSMIC database. The study design allows us to assess the effects of the number of mutations, type of cancer, and the catalog of reference signatures on the results obtained with various fitting tools. We find substantial performance differences between the evaluated tools. Averaged over 120,000 simulated mutational catalogs corresponding to eight different cancer types, SigProfilerSingleSample and SigProfilerAssignment perform best for small and large numbers of mutations per sample, respectively. We further show that ad hoc constraining the list of reference signatures is likely to produce inferior results and that noisy estimates of signature weights in samples with as few as 100 mutations can still be useful in downstream analysis. Cancer genomics, statistical methods, mutational signatures, computational models Keywords: 1. Introduction Since their introduction a decade ago by Nik-Zainal et al. (2012), Alexandrov et al. (2013), mutational signatures have become a widely used tool in genomics (Maura et al., 2019, Koh et al., 2021). They allow researchers to move from individual mutations in the genome to biological processes that take place in living tissues (Kim et al., 2021). In (Cannataro et al., 2022), for example, signature activities have been used to attribute mutations to endogenous, exogenous, and preventable mutational processes. The activity of various mutational signatures can also serve as prognostic or therapeutic biomarkers (Van Hoeck et al., 2019, Brady et al., 2022). Homologous recombination defficiency leads to the accumulation of DNA damage and manifests itself in a specific mutational signature (signature SBS3 from the COSMIC catalog) (Nik-Zainal et al., 2016, Gulhan et al., 2019). Mutational signatures can be introduced for single base substitutions (SBS), doublet base substitutions (DBS), small insertions and deletions (ID), as well as for copy number variations (CN). We focus here on SBS-based mutational signatures which are most commonly used in the literature. Current SBS signatures are defined using 6 possible classes of substitutions (C>A, C>G, C>T, T>A, T>C, and T>G) together with their two immediate neighboring bases, thus giving rise to 6 × 4 × 4 = 96 different nucleotide contexts into which all SBS mutations in a given sample are classified. De novo extraction of signatures from somatic mutations in sequenced samples has been used to gradually map the landscape of mutational signatures in cancer tissues. Over time, the initial catalogue of 22 SBS-based mutational signatures in the first version of the Catalogue Of Somatic Mutations In Cancer (COSMIC) released in August 2013 has expanded to 80 signatures in the COSMICv3.3 version released in June 2022. This expansion was possible owing to the increased availability of WES and WGS sequencing data as well as improved tools for signature extraction. Extensive benchmarking of extraction tools on synthetic data has recently shown that SigProfilerExtractor outperforms other methods in terms of sensitivity, precision, and false discovery rate, particularly in cohorts with more than 20 active signatures (Islam et al., 2022). A two-step process consisting of first extracting common signatures and then rare signatures has been recently recommended in (Degasperi et al., 2022). Nevertheless, with the existing signatures extracted from cohorts including thousands of sequenced samples (Alexandrov et al., 2020, Islam et al., 2022, Degasperi et al., 2022), the authors of smaller studies are unlikely to discover new signatures. For example, the analysis of more than 23,000 WGS and WES cancers in (Islam et al., 2022) has only discovered four new signatures. The much more relevant task is thus that of fitting existing signatures to given sequenced samples. In this process, the catalogs of somatic mutations are used to determine the signature contributions to each individual sample. Many different tools have been developed for this task (Koh et al., 2021) (see Methods for their description and classification). However, while tools for extracting mutational signatures have been recently extensively benchmarked on synthetic data by various studies (Omichessan et al., 2019, Alexandrov et al., 2020, Islam et al., 2022, Wu et al., 2022), a similar quantitative comparison is lacking for tools for fitting mutational signatures. This need is further exacerbated by substantial variations between results obtained by different methods (Pandey et al., 2022). Furthermore, newly introduced tools for fitting mutational signatures are commonly compared with only a few existing tools, rarely the most recent ones, and a standardized comparison methodology is lacking. In this study, our aim is to fill this gap and provide a comprehensive evaluation of a broad range of fitting tools on synthetic data motivated by various types of cancer. We constrain on fitting SBS signatures as they are the most widely used signature type. Many of the included tools can be nevertheless used for other types of signatures as their fitting is mathematically not different from the fitting of SBS signatures. We generate two classes of synthetic mutational catalogs. In the first one, only one mutational signature is responsible for all mutations (single-signature cohorts). In the second one, signature activities in each sample are modeled after the activities found in real tumor samples from various cancers (heterogeneous cohorts). We have collected eleven tools for fitting mutational signatures, from earlier tools such as deconstructSigs to very recent ones such as SigProfilerAssignment. We assess their performance by comparing the known true signature activities in the created catalogs with results obtained by various fitting tools. We find that there is no single fitting tool that performs best regardless of how many mutations are in the samples and which cancer type is chosen to model signature activities. Averaged across all cancer types, two related tools (SigProfilerSingleSample and SigProfilerAssignment) perform best when the number of mutations per sample is small (below 1000, roughly) and large (above 1000), respectively. We also compare the tools by how prone they are to overfitting caused by increasing the size of the reference signature catalog and evaluate whether it is beneficial to constrain the reference catalog based on which signatures seem to be absent or little active in the analyzed samples. We close with a discussion of open problems in fitting mutational signatures. Figure 1: (a, b) The bars show the 95th percentile range of the observed fraction of mutations in synthetic data for SBS mutational contexts (horizontal axis) and different total mutation counts (100, 1,000 and 10,000 represented with red, blue and gray bars, respectively). The effect of the number of mutations in single-signature cohorts. Panels a and b show signature SBS1 with four distinct C>T peaks and signature SBS5 with a flat mutational spectrum, respectively. (c) The fitting errors of the evaluated fitting tools for synthetic data corresponding to 100 samples with 100% contributions of a single signature; the catalog of all 67 COSMICv3 signatures was used for fitting. We show results for ten common signatures (horizontal axis) and various mutation counts (vertical axis). The tools are ordered by the error averaged over the displayed signatures achieved for 51,200 mutations. This paper is available on under CC 4.0 license. arxiv

A Comprehensive Comparison of Tools for Fitting Mutational Signatures

This paper is available on arxiv under CC 4.0 license. Authors: (1) Ali Ghanbari, Dept. of Computer Science, Iowa State University; (2) Deepak-George Thomas, Dept. of Computer Science, Iowa State University; (3) Muhammad Arbab Arshad, Dept. of Computer Science, Iowa State University; (4) Hridesh Rajan, Dept. of Computer Science, Iowa State University. Table of Links Abstract & Introduction Background Motivating Example Proposed Approach Supported DNN Bugs Evaluation Threats to Validity Related Work Conclusion, Acknowledgments & References VII. THREATS TO VALIDITY As with most empirical evaluations, we do not have a working definition of representative sample of DNN bugs, but we made efforts to ensure that the bugs we used in the evaluation is as representative as possible by making sure that our dataset has diverse examples of bugs from each subcategory of model bugs. ategory of model bugs. Many of the bugs obtained from StackOverflow did not come with accompanying training datasets. To address this issue, we utilized the dataset generation API provided by scikit-learn [64] to generate synthetic datasets for regression or classification tasks. We ensured that the errors described in each StackOverflow post would manifest when using the synthesized data points and that applying the fix suggested in the accepted response post would eliminate the bug. However, it is possible that this change to the training process may introduce new unknown bugs. To mitigate this risk, we have made our bug benchmark publicly available [36]. Another potential threat to the validity of our results is the possibility of bugs in the construction of deepmufl itself, which could lead to incorrect bug localization. To mitigate this, we make the source code of deepmufl publicly available for other researchers to review and validate the tool. Another threat to the validity of our results is the potential impact of external factors, such as the stochastic nature of the training process and the synthesized training/testing datasets, as well as system load, on our measurements. To address this, besides using deterministic seeds for dataset generation and splitting, we repeated our experiments with deepmufl three times. Similarly, we also ran other dynamic tools three times to ensure that their results were not affected by randomness during training. We did not observe any differences in effectiveness between the rounds for either deepmufl or the other studied techniques. Additionally, we repeated the time measurements for each round, and reported the average timing, to ensure that our time measurements were not affected by system load. Furthermore, judging whether or not any of the tools detect a bug requires manual analysis of textual description of the bugs and matching it to the tools; output messages which might be subject to bias. To mitigate this bias, we have made the output messages by the tools available for other researchers [36]. Lastly, deepmufl uses a threshold parameter to compare floating-point values (see §IV-C). In our experiments, we used the default value of 0.001 and ensured that smaller threshold values yield the same results.

Mutation-based Fault Localization of Deep Neural Networks: Threats to Validity

This paper is available on arxiv under CC 4.0 license. Authors: (1) Ali Ghanbari, Dept. of Computer Science, Iowa State University; (2) Deepak-George Thomas, Dept. of Computer Science, Iowa State University; (3) Muhammad Arbab Arshad, Dept. of Computer Science, Iowa State University; (4) Hridesh Rajan, Dept. of Computer Science, Iowa State University. Table of Links Abstract & Introduction Background Motivating Example Proposed Approach Supported DNN Bugs Evaluation Threats to Validity Related Work Conclusion, Acknowledgments & References VIII. RELATED WORK Neuralint [12] uses graph transformations [65] to abstract away unnecessary details in the model and check the bug patterns directly on the graph. While Neuralint is orders of magnitude faster than deepmufl, it proved to be less effective than deepmufl in our dataset. DeepLocalize [11] and DeepDiagnosis [8] intercept the training process looking for known bug patterns such as numerical errors. DeepDiagnosis pushes the envelope by implementing a decision tree that gives actionable fix suggestions based on the detected symptoms. A closely related technique, UMLAUT [34], works by applying heuristic static checks on, and injecting dynamic checks in, various parts of the DNN program. deepmufl outperforms DeepLocalize, DeepDiagnosis, and UMLAUT in terms of the number of bugs detected. DeepFD [66] is a recent learning-based fault localization technique which frames the fault localization as a learning problem. MODE [25] and DeepFault [26] implement whitebox DNN testing technique which utilizes suspiciousness values obtained via an implementation of spectrum-based fault localization to increase the hit spectrum of neurons and identify suspicious neurons whose weights have not been calibrated correctly and thus are considered responsible for inadequate DNN performance. MODE was not publicly available, but DeepFault was, but unfortunately it was hard-coded to the examples shipped with its replication package, so we could not make the tool work without making substantial modifications to it, not to mention that these techniques work best on ReLUbased networks and applying them on most of the bugs in our dataset would not make much sense. Other related works are as follows. PAFL [67] operates on RNN models by converting such models into probabilistic finite automata (PFAs) and localize faulty sequences of state transitions on PFAs. Sun et al. [68] propose DeepCover, which uses a variant of spectrum-based fault localization for DNN explainability.

Mutation-based Fault Localization of Deep Neural Networks: Related Work

This paper is available on arxiv under CC 4.0 license. Authors: (1) Ali Ghanbari, Dept. of Computer Science, Iowa State University; (2) Deepak-George Thomas, Dept. of Computer Science, Iowa State University; (3) Muhammad Arbab Arshad, Dept. of Computer Science, Iowa State University; (4) Hridesh Rajan, Dept. of Computer Science, Iowa State University. Table of Links Abstract & Introduction Background Motivating Example Proposed Approach Supported DNN Bugs Evaluation Threats to Validity Related Work Conclusion, Acknowledgments & References IX. CONCLUSION This paper revisits mutation-based fault localization in the context of DNN and presents a novel DNN fault localization technique, named deepmufl. The technique is based on the idea of mutating a pre-trained DNN model and calculating suspiciousness values according to Metallaxis and MUSE approaches, Ochiai and SBI formulas, and two types of impacts of mutations on the results of test data points. deepmufl is compared to state-of-the-art static and dynamic fault localization systems [11], [8], [34], [12] on a benchmark of 109 model bugs. In this benchmark, while deepmufl is slower than the other tools, it proved to be almost two times more effective than them in terms of the total number of bugs detected and it detects 21 bugs that none of the studied tools were able to detect. We further studied the impact of mutation selection on fault localization time. We observed that we can halve the time taken to perform fault localization by deepmufl, while losing only 7.55% of the previously detected bugs. ACKNOWLEDGMENTS The authors thank Anonymous ASE 2023 Reviewers for their valuable feedback. We also thank Mohammad Wardat for his instructions on querying StackOverflow. This material is based upon work supported by the National Science Foundation (NSF) under the grant #2127309 to the Computing Research Association for the CIFellows Project. This work is also partially supported by the NSF grants #2223812, #2120448, and #1934884. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF. REFERENCES [1] IEEE Standard Classification for Software Anomalies, 2010. [2] A. McPeak, “What’s the true cost of a software bug?” https://smartbear. com/blog/software-bug-cost/, 2017, accessed 08/10/23. [3] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” Nature, vol. 521, no. 7553, pp. 436–444, 2015. [4] M. J. Islam, G. Nguyen, R. Pan, and H. Rajan, “A comprehensive study on deep learning bug characteristics,” in ESEC/FSE, 2019, pp. 510–520. [5] M. J. Islam, R. Pan, G. Nguyen, and H. Rajan, “Repairing deep neural networks: Fix patterns and challenges,” in ICSE, 2020, pp. 1135–1146. [6] Y. Zhang, Y. Chen, S.-C. Cheung, Y. Xiong, and L. Zhang, “An empirical study on tensorflow program bugs,” in ISSTA, 2018, pp. 129–140. [7] N. Humbatova, G. Jahangirova, G. Bavota, V. Riccio, A. Stocco, and P. Tonella, “Taxonomy of real faults in deep learning systems,” in ICSE, 2020, pp. 1110–1121. [8] M. Wardat, B. D. Cruz, W. Le, and H. Rajan, “Deepdiagnosis: automatically diagnosing faults and recommending actionable fixes in deep learning programs,” in ICSE. IEEE, 2022, pp. 561–572. [9] K. Pei, Y. Cao, J. Yang, and S. Jana, “Deepxplore: Automated whitebox testing of deep learning systems,” in SOSP, 2017, pp. 1–18. [10] J. Kim, R. Feldt, and S. Yoo, “Guiding deep learning system testing using surprise adequacy,” in ICSE, 2019, pp. 1039–1049. [11] M. Wardat, W. Le, and H. Rajan, “Deeplocalize: fault localization for deep neural networks,” in ICSE, 2021, pp. 251–262. [12] A. Nikanjam, H. B. Braiek, M. M. Morovati, and F. Khomh, “Automatic fault detection for deep learning programs using graph transformations,” TOSEM, vol. 31, no. 1, pp. 1–27, 2021. [13] M. Usman, D. Gopinath, Y. Sun, Y. Noller, and C. S. Pas˘ areanu, “Nn ˘ repair: Constraint-based repair of neural network classifiers,” in CAV, 2021, pp. 3–25. [14] X. Zhang, J. Zhai, S. Ma, and C. Shen, “Autotrainer: An automatic dnn training problem detection and repair system,” in ICSE, 2021, pp. 359–371. [15] W. E. Wong, R. Gao, Y. Li, R. Abreu, and F. Wotawa, “A survey on software fault localization,” TSE, vol. 42, no. 8, pp. 707–740, 2016. [16] M. Papadakis and Y. Le Traon, “Using mutants to locate” unknown” faults,” in ICST, 2012, pp. 691–700. [17] S. Moon, Y. Kim, M. Kim, and S. Yoo, “Ask the mutants: Mutating faulty programs for fault localization,” in ICST, 2014, pp. 153–162. [18] R. A. DeMillo, R. J. Lipton, and F. G. Sayward, “Hints on test data selection: Help for the practicing programmer,” IEEE Computer, vol. 11, pp. 34–41, 1978. [19] R. Abreu, P. Zoeteweij, and A. J. Van Gemund, “On the accuracy of spectrum-based fault localization,” in TAICPART-MUTATION, 2007, pp. 89–98. [20] V. Dallmeier, C. Lindig, and A. Zeller, “Lightweight Bug Localization with AMPLE,” in ISAADD, 2005, pp. 99–104. [21] J. A. Jones, M. J. Harrold, and J. Stasko, “Visualization of test information to assist fault localization,” in ICSE, 2002, pp. 467–477. [22] L. Naish, H. J. Lee, and K. Ramamohanarao, “A model for spectra-based software diagnosis,” TOSEM, vol. 20, no. 3, pp. 1–32, 2011. [23] S. Yoo, “Evolving human competitive spectra-based fault localisation techniques,” in SBSE, 2012, pp. 244–258. [24] X. Xie, F.-C. Kuo, T. Y. Chen, S. Yoo, and M. Harman, “Provably optimal and human-competitive results in sbse for spectrum based fault localisation,” in SBSE, 2013, pp. 224–238. [25] S. Ma, Y. Liu, W.-C. Lee, X. Zhang, and A. Grama, “Mode: automated neural network model debugging via state differential analysis and input selection,” in ESEC/FSE, 2018, pp. 175–186. [26] H. F. Eniser, S. Gerasimou, and A. Sen, “Deepfault: Fault localization for deep neural networks,” in FASE, 2019, pp. 171–191. [27] N. Humbatova, G. Jahangirova, and P. Tonella, “Deepcrime: mutation testing of deep learning systems based on real faults,” in ISSTA, 2021, pp. 67–78. [28] Q. Hu, L. Ma, X. Xie, B. Yu, Y. Liu, and J. Zhao, “Deepmutation++: A mutation testing framework for deep learning systems,” in ASE, 2019, pp. 1158–1161. [29] L. Ma, F. Zhang, J. Sun, M. Xue, B. Li, F. Juefei-Xu, C. Xie, L. Li, Y. Liu, J. Zhao et al., “Deepmutation: Mutation testing of deep learning systems,” in ISSRE, 2018, pp. 100–111. [30] M. Papadakis and Y. Le Traon, “Metallaxis-fl: mutation-based fault localization,” STVR, vol. 25, no. 5-7, pp. 605–628, 2015. [31] F. Chollet et al., “Keras,” https://keras.io, 2015. [32] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur, J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner, P. Tucker, V. Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng, “Tensorflow: A system for large-scale machine learning,” in OSDI, 2016, p. 265–283. [33] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “Pytorch: An imperative style, highperformance deep learning library,” in NIPS, 2019, pp. 8024–8035. [34] E. Schoop, F. Huang, and B. Hartmann, “Umlaut: Debugging deep learning programs using program structure and model behavior,” in CHI, 2021, pp. 1–16. [35] W. E. Wong and A. P. Mathur, “Reducing the cost of mutation testing: An empirical study,” JSS, pp. 185–196, 1995. [36] A. Ghanbari, D.-G. Thomas, M. A. Arshad, and H. Rajan, “Mutationbased fault localization of deep neural networks,” https://github.com/ ali-ghanbari/deepmufl-ase-2023, 2023. 37] J. H. Andrews, L. C. Briand, and Y. Labiche, “Is mutation an appropriate tool for testing experiments?” in ICSE, 2005, pp. 402–411. [38] M. Papadakis, M. Kintis, J. Zhang, Y. Jia, Y. Le Traon, and M. Harman, “Mutation testing advances: an analysis and survey,” in Advances in Computers, 2019, vol. 112, pp. 275–378. [39] V. Debroy and W. E. Wong, “Using mutation to automatically suggest fixes for faulty programs,” in ICST, 2010, pp. 65–74. [40] A. Ghanbari, S. Benton, and L. Zhang, “Practical program repair via bytecode mutation,” in ISSTA, 2019, pp. 19–30. [41] G. Fraser and A. Arcuri, “Achieving scalable mutation-based generation of whole test suites,” ESE, pp. 783–812, 2015. [42] F. C. M. Souza, M. Papadakis, Y. Le Traon, and M. E. Delamaro, “Strong mutation-based test data generation using hill climbing,” in IWSBST, 2016, pp. 45–54. [43] D. Shin, S. Yoo, M. Papadakis, and D.-H. Bae, “Empirical evaluation of mutation-based test case prioritization techniques,” STVR, p. e1695, 2019. [44] J. P. Galeotti, C. A. Furia, E. May, G. Fraser, and A. Zeller, “Inferring loop invariants by mutation, dynamic analysis, and static checking,” TSE, pp. 1019–1037, 2015. [45] A. Groce, I. Ahmed, C. Jensen, and P. E. McKenney, “How verified is my code? falsification-driven verification (t),” in ASE, 2015, pp. 737– 748. [46] B. Liblit, M. Naik, A. X. Zheng, A. Aiken, and M. I. Jordan, “Scalable statistical bug isolation,” ACM SIGPLAN Notices, vol. 40, no. 6, pp. 15–26, 2005. [47] R. Abreu, P. Zoeteweij, and A. J. Van Gemund, “An evaluation of similarity coefficients for software fault localization,” in PRDC, 2006, pp. 39–46. [48] Wikipedia contributors, “Hierarchical data format — Wikipedia, the free encyclopedia,” 2022, accessed 08/10/23. [49] H. Coles, T. Laurent, C. Henard, M. Papadakis, and A. Ventresque, “Pit: a practical mutation testing tool for java,” in ISSTA, 2016, pp. 449–452. [50] P. Ammann and J. Offutt, Introduction to software testing. Cambridge University Press, 2016. [51] R. Just, F. Schweiggert, and G. M. Kapfhammer, “Major: An efficient and extensible tool for mutation analysis in a java compiler,” in ASE, 2011, pp. 612–615. [52] Y.-S. Ma, J. Offutt, and Y. R. Kwon, “Mujava: an automated class mutation system,” STVR, pp. 97–133, 2005. [53] D. Schuler and A. Zeller, “Javalanche: Efficient mutation testing for java,” in ESEC/FSE, 2009, pp. 297–298. [54] “Junit,” http://junit.org/, 2019, accessed 08/10/23. [55] “Testng documentation,” https://testng.org/doc/documentation-main. html, 2017, accessed 08/10/23. [56] M. M. Morovati, A. Nikanjam, F. Khomh, Z. Ming et al., “Bugs in machine learning-based systems: A faultload benchmark,” arXiv, 2022. [57] X. Li and L. Zhang, “Transforming programs and tests in tandem for fault localization,” Proceedings of the ACM on Programming Languages, vol. 1, no. OOPSLA, pp. 1–30, 2017. [58] C. Parnin and A. Orso, “Are automated debugging techniques actually helping programmers?” in ISSTA, 2011, pp. 199–209. [59] P. S. Kochhar, X. Xia, D. Lo, and S. Li, “Practitioners’ expectations on automated fault localization,” in ISSTA, 2016, pp. 165–176. [60] D. Shin and D.-H. Bae, “A theoretical framework for understanding mutation-based testing methods,” in ICST, 2016, pp. 299–308. [61] A. V. Pizzoleto, F. C. Ferrari, J. Offutt, L. Fernandes, and M. Ribeiro, “A systematic literature review of techniques and metrics to reduce the cost of mutation testing,” Journal of Systems and Software, vol. 157, p. 110388, 2019. [62] J. Zhang, “Scalability studies on selective mutation testing,” in ICSE, vol. 2, 2015, pp. 851–854. [63] A. J. Offutt, J. Pan, K. Tewary, and T. Zhang, “An experimental evaluation of data flow and mutation testing,” Software: Practice and Experience, vol. 26, no. 2, pp. 165–176, 1996. [64] scikit-learn Contributors, “scikit-learn: Machine learning in python,” 2020, accessed 08/10/23. [Online]. Available: https://scikit-learn.org/stable/ [65] R. Heckel, “Graph transformation in a nutshell,” ENTCS, vol. 148, no. 1, pp. 187–198, 2006. [66] J. Cao, M. Li, X. Chen, M. Wen, Y. Tian, B. Wu, and S.-C. Cheung, “Deepfd: Automated fault diagnosis and localization for deep learning programs,” in ICSE, 2022, p. 573–585. [67] Y. Ishimoto, M. Kondo, N. Ubayashi, and Y. Kamei, “Pafl: Probabilistic automaton-based fault localization for recurrent neural networks,” IST, vol. 155, p. 107117, 2023. [68] Y. Sun, H. Chockler, X. Huang, and D. Kroening, “Explaining image classifiers using statistical fault localization,” in ECCV, 2020, pp. 391–406.

Mutation-based Fault Localization of Deep Neural Networks: Conclusion, Acknowledgments & References

This paper is available on arxiv under CC 4.0 license. Authors: (1) Ali Ghanbari, Dept. of Computer Science, Iowa State University; (2) Deepak-George Thomas, Dept. of Computer Science, Iowa State University; (3) Muhammad Arbab Arshad, Dept. of Computer Science, Iowa State University; (4) Hridesh Rajan, Dept. of Computer Science, Iowa State University. Table of Links Abstract & Introduction Background Motivating Example Proposed Approach Supported DNN Bugs Evaluation Threats to Validity Related Work Conclusion, Acknowledgments & References IV. PROPOSED APPROACH Our technique deepmufl comprises four components: (1) mutation generator, (2) test case splitter, (3) mutation executor/tester, and (4) suspiciousness calculator. Figure 2 depicts these components as processes, numbered accordingly, taking inputs and producing outputs. Mutation generator (marked ⃝1 in Figure 2), applies 79 mutators on all the layers of the input buggy DNN, so as to generate a pool of mutants, i.e., variants of the original, buggy DNN model with small perturbations, e.g., replacing activation function of a layer. Test case splitter (marked ⃝2 in the figure), applies the original buggy DNN on a given set of test data points, i.e., test cases (or input values) paired with their expected output values, so as to partition the set into two subset, namely passing test cases and failing test cases. Passing test cases are referred to as those input values for which the expected output matches that of produced by the original model, whereas failing test cases are referred to as those input values for which the expected output does not match that of produced by the model. This component also stores the output of the original model on each of the test cases. Next, mutation executor (which is also called mutation tester, marked ⃝3 in the figure) applies the generated mutants on each of the passing and failing test cases and the results are compared to that of the original model recorded in the previous step. This amounts to a mutation execution matrix that is used to calculate suspiciousness values for each layer in the model (marked ⃝4 in the figure). The user may instruct deepmufl to use a specific fault localization formula, e.g., MUSE or Metallaxis with SBI or Ochiai, for calculating suspiciousness values. The layers are then ranked based on the calculated suspiciousness values for user inspection. The ranked list is accompanied with the information about the mutations conducted on each layer to facilitate debugging. A. Mutation Generator Mutation generator component receives the original, buggy DNN model and generates as many variants of the model, i.e., mutants, as possible, by systematically mutating every elements of the input model. This component implements 79 mutators. Mutators can be viewed as transformation operators that when applied to a given element, e.g., a neuron or a layer, in the model, returns a new variants of the model with that particular element mutated. Table 2 lists all the mutators implemented in deepmufl, the types of model elements on which they can operate, and the way each mutator affects the target element. These mutators are inspired by the ones implemented in the existing mutation analysis systems, e.g., [27], [28], [29], [49], [50], [51], [52], [53], to name a few. Ma et al. [29], and Hu et al. [28], define so-called model-level mutators that also operate on pre-trained models. Direct reuse of all of their mutators was not possible, as those mutators depend on random values which would introduce a source of nondeterminism in deepmufl: mutating the same model element with random values, e.g., Gaussian fuzzing, as in [29], would yield a different mutant each time, making deepmufl to produce different outputs on each run for the same model. In general, as far as MBFL is concerned, using variable values (whether it is deteministic or not), instead of the current hard-coded ones, for mutation of weights would not bring about any benefit, as the goal here is to break the model in some way and observe its impact on originally failing and passing test cases. We argue that not all model bugs could be emulated using mutators at the level of pre-trained models, e.g., missing batch normalization, but the mutators listed in Table 2 are sufficient for emulating a subset of such bugs, e.g., wrong activation function or missing/redundant layer. Please see §V for a more detailed discussion on supported bugs. Mutation generation in deepmufl is done directly on the trained model and there is no need for retraining the model. This makes deepmufl quite fast and perhaps more attractive from a practical point of view. However, this comes with a risk of not being traceable, i.e., a mutation on pre-trained .h5 model does not directly correspond to a line of source code for the user to inspect. In the Keras programs that we studied, this limitation was mitigated by the fact that the models with Sequential architecture were implemented using a wellunderstood structure and mapping layer numbers/identifiers in deepmufl’s reports to source code was trivial. In a future work, with the help of simple auto-generated annotations, e.g., for lexical scoping of the code snippet for model declaration, we will extend deepmufl to automatically map layer numbers/identifiers in its reports to actual lines of source code. Humbatova et al. [27] argue about the importance of mutators emulating real DNN faults. We acknowledge that mutators emulating real faults would help generating more informative reports that would also give hints on how to fix the program. However, unlike mutation analysis, the main objective of an MBFL technique is to assign suspiciousness values to the program elements which can, in theory, be done using any kind of mutator, whether or not it makes sense from the standpoint of a developer. It is worth noting that the alternative design decision of using DeepCrime [27] as a mutation generation engine for deepmufl would result in finding more bugs than the current version of deepmufl, e.g., bugs related to training hyper-parameters or training dataset, but such a design is expected to be impacted by the nondeterminacy inherent in training process and, given the fact that we do not employ any training data selection, would be significantly slower due to numerous re-training. Nevertheless, finding more bugs would be an incentive for exploring this alternative as a future work. B. Test Case Splitter Before we introduce this component, we need to clarify certain terminology. .** Definition 1 A data point in a testing dataset for a DNN model is defined to be a pair of the form (I, O), where I ∈ R m and O ∈ R n, with m and n being positive integers. In this paper I is called test case, test input, or input, while O is called expected output or ground-truth value. Given a test dataset, test case splitter component applies the original model on each of the test cases for the data points and checks if the model output matches to the expected output. If the two outputs match, then the corresponding test case will be marked as passing, otherwise it will be marked as failing. This component also records the output produced by the original model to be used during impact analysis, described below. C. Mutation Executor (Mutation Tester) We start describing this component with a definition. Definition 2. A mutation execution matrix E is a k×l matrix, where k is the number of generated mutants, while l is the number of test cases. Each element Ei,j in the matrix is a member of the set {✓, ✗, ❍}, wherein ✓ indicates that the i th mutant impacts j th test case, whereas ✗ indicates that the mutant does not affect the test case. ❍ denotes a nonviable mutant, i.e., a mutant that fails when loading or applying it on a test case. Such mutants might be generated, e.g., due to creating a shape error [32] after the mutation. Mutation executor component construct mutation execution matrix by applying each of the generated mutants (see §IV-A) on the failing and passing test cases to determine which of the test cases are impacted by which mutants. The impact of mutation on test cases is measured using two types of impacts, i.e., type 1 impact and type 2 impact, defined below. Definition 3. Given a DNN model M, its mutated version M′ , and a data point (I, O), we define the two types of impacts: • Type 1: Mutant M′ impacts the test case I if M(I) = O but M′ (I) ̸= O, or M(I) ̸= O but M′ (I) = O. In other words, type 1 impact tracks pass to fail and fail to pass test cases, a la MUSE [17]. ` • Type 2: Mutant M′ impacts the test case I if M(I) ̸= M′ (I). In this definition, M(I) or M′ (I) denotes the operation of applying model M or M′ on the test case I. It is worth noting that checking for equality of two values can be tricky for regression models, as those models approximate the expected values. To work around this problem, deepmufl compares values obtained from regression models using a user-defined delta threshold, i.e., the values are deemed equal if their absolute difference is no more than a threshold. By default, deepmufl uses a threshold of 0.001. This is the approach adopted by well-known testing frameworks for comparing floating-point values [54], [55]. Also, whether deepmufl uses type 1 or type 2 impact is a user preference and is determined alongside the threshold. D. Suspiciousness Value Calculator Armed with the above definitions, we can now give concrete definitions for the terms used in Eq. 1, 2, and 3, specialized to DNNs. • Given a model element, i.e., neuron or a layer, e, M(e) is defined to be the set of all mutants generated by mutating e. These sets are produced by mutation generator process. • Assuming that m is a mutant on the element e, Tf (m, e) (or Tp(m, e)) is defined as the set of failing (or passing) test cases that are impacted in type 1 or type 2 fashion by m. More concretely, Tp(m, e) = {t | Em,t = ✓ ∧ t is passing}, similarly Tf (m, e) = {t | Em,t = ✓ ∧ t is failing}. These two sets are defined using a quite similar notation; the readers are encouraged to review Definitions 2 and 3 to avoid confusion. • Tf (or Tp) is the set of originally failing (or passing) test cases. These sets are constructed by test case splitter. • F ⇝ P (or P ⇝ F), for a model element e, is defined as the set of originally failing (or passing) test cases that turned into passing (or failing) as a result of some mutation on e. More concretely, assuming the execution matrix E is constructed using type 1 impact, F ⇝ P is defined as {t | t is failing ∧ ∃m ∈ M(e) · Em,t = ✓}. Similarly, P ⇝ F is defined as {t | t is passing ∧ ∃m ∈ M(e)·Em,t = ✓}. In other words, these sets track all the failing/passing test cases that are type 1 impacted by some mutant of a given element. These two sets are defined using a quite similar notation; the readers are encouraged to review Definitions 2 and 3 to avoid confusion. Having specialized definitions for the terms used in the fault localization formulas described earlier, we are now able to calculate suspiciousness values for the elements in a DNN model. Guided by the user preferences, deepmufl calculates all the values for |Tf (m, e)|, etc., and plugs into the specified formula to calculate suspiciousness values for the elements. It is worth noting that if all the mutants generated for a given element are nonviable, MUSE formula (Eq. 3) and all the variants of Metallaxis (e.g., Eq. 1), by definition, will return 0 as the suspiciousness value for the element. Nonviable mutants do not contribute toward localizing the bug, therefore they are considered overhead to the fault localization process. Fortunately, based on our observations in our dataset of buggy DNNs, nonviable mutants are rare. Equivalent mutants are another source of overhead for deepmufl. Currently, we do not have any means of detecting equivalent mutants, but we argue that these mutants do not impact MBFL results, as they are equivalent to the original model and do not impact any passing or failing test cases.

Mutation-based Fault Localization of Deep Neural Networks: Proposed Approach

This paper is available on arxiv under CC 4.0 license. Authors: (1) Ali Ghanbari, Dept. of Computer Science, Iowa State University; (2) Deepak-George Thomas, Dept. of Computer Science, Iowa State University; (3) Muhammad Arbab Arshad, Dept. of Computer Science, Iowa State University; (4) Hridesh Rajan, Dept. of Computer Science, Iowa State University. Table of Links Abstract & Introduction Background Motivating Example Proposed Approach Supported DNN Bugs Evaluation Threats to Validity Related Work Conclusion, Acknowledgments & References VI. EVALUATION We evaluate deepmufl and compare it to state-of-the-art static and dynamic DNN fault localization techniques, by investigating the following research questions (RQs). • RQ1 (Effectiveness): How does deepmufl compare to state-of-the-art tools in terms of the number of bugs detected? How many bugs does deepmufl detect from each subcategory of model bugs in our dataset and how does that compare to state-of-the-art tools? What are the overlap of detected bugs among deepmufl and other fault localization techniques? • RQ2 (Efficiency): What is the impact of mutation selection on the effectiveness and efficiency of deepmufl? How does deepmufl compare to state-of-the-art tools in terms of end-to-end fault localization time? A. Dataset of DNN Bugs To evaluate deepmufl and compare it to state-of-the-art DNN fault localization techniques, we queried StackOverflow Q&A website for posts about Keras that had at least one accepted answer. Details about the SQL query used to obtain the initial list of posts is available online [36]. The query resulted in 8,412 posts that we manually sieved through to find the programs with model bugs. Specifically, we kept the bugs that satisfied the following conditions. • Implemented using Sequential API of Keras, • The bug in the program was a model bug supported by deepmufl as described in §V, and • The bug either had training datatset available in the post in some form (e.g., hard-coded, clearly described in the body of the post, or a link to the actual data was provided) or we could see the described error using synthetic data obtained from scikit-learn’s dataset generation API. This resulted in 102 bugs and we paired each bug with a fix obtained from the accepted answer to the question. We further added 7 bugs from DeepLocalize dataset [11] that are also coming from StackOverflow and we paired these bugs also with their fixes that are obtained from the most up-voted answer. Thus, we ended up with 109 bugs in total. To the best of our knowledge, this is the largest dataset of model bugs obtained from StackOverflow and it overlaps with the existing DNN bug datasets from previous research [12], [56]. Our bug dataset contains 85 classifiers (45 fully-connected DNNs, 29 CNNs, and 11 RNNs) and 24 regression models (19 fullyconnected DNNs, 3 CNNs, and 2 RNNs). And each category has at least one example of model bugs. Therefore, we believe that our dataset is greatly representative of model bugs, i.e., the bugs supported by deepmufl (and other tools that support this type of bugs), as we have examples of each sub-category of bug in various locations of the models for various regression and classification tasks. After loading the training dataset for the bugs, we fitted the buggy models three times and stored them in .h5 file format separately. The repetition was conducted to take randomness in training into account. Randomness in data generation was mitigated by using deterministic random seeds. For fault localization purposes, we used the test dataset, and if it was not available, we used the training dataset itself. When we had to use synthesized data points, we deterministically splitted the generated set of data into training and testing datasets. B. Baseline Approaches and Measures of Effectiveness In RQ1 and RQ2, we compare five different configurations of deepmufl to recent static and dynamic DNN fault localization tools. The five configurations of deepmufl are as follows. • [30]: In this setting, we use the Metallaxis formula to calculate suspiciousness values of model elements. Metallaxis, by default, uses SBI [46] to calculate suspiciousness values for individual mutants. A recent study [57] provides empirical evidence on the superiority of Ochiai [47] over SBI when used within Metallaxis formula. Thus, we considered the following four combinations: type 1 impact: (1) SBI formula (i.e., Eq. 1); (2) Ochiai formula (i.e., Eq. 2), and type 2 impact: (3) SBI formula (i.e., Eq. 1); (4) Ochiai formula (i.e., Eq. 2). Metallaxis • [17]: We used the default formula of MUSE to calculate the suspiciousness of model elements. For this, only type 1 impact is considered, as the heuristics behind MUSE are defined based on type 1 impact. MUSE Our technique follows a more traditional way of reporting root causes for the bugs [30], [17], [57], [19], [22], [21], [15], in that it reports a list of potential root causes ranked based on the likelihood of being responsible for the bug. This allows the users find the bugs faster and spend less time reading through the fault localization report, which in turn increases practicality of the technique [58]. We have used top-N, with N = 1, metric to measure the effectiveness of deepmufl in RQ1 and RQ2. Specifically, if the numbers of any of the buggy layers of the bug appeared in the first place in the output of deepmufl, we reported it as detected, otherwise we marked the bug as not-detected. We emphasize that top-1 metric gives a strong evidence on the effectiveness of deepmufl, as the developers usually only inspect top-ranked elements, e.g., over 70% of the developers only check top-5 ranked elements [59]. Our selection criteria for the studied fault localization techniques are: (1) availability; (2) reproducibility of the results reported in the original papers, so as to have a level of confidence on the correctness of the results reported here; and (3) support for model bugs in our dataset, so that we can make a meaningful comparison to deepmufl. Below we give a brief description of each of the selected tools, why we believe they support model bugs, and how we have interpreted their outputs in our experiments, i.e., when we regard a bug being detected by the tool. A static fault localization tool that uses 23 rules to detect faults and design inefficiencies in the model. Each rule is associated with a set of rules of thumb to fix the bug that are shown to the user in case the precondition for any of the rules are satisfied. The five rules described in Section 4.2.1 of the paper target model bugs. Neuralint produces outputs of the form [Layer L ==> MSG] ∗ , where L is the suspicious layer number, and MSG is a description of the detected issue and/or suggestion on how to fix the problem. A bug is deemed detected by this tool if it is located in the layer mentioned in the output message or the messages describe any of the root causes of the bug. 1) Neuralint: A dynamic fault localization technique that detects numerical errors during model training. One of three rules described in Section III.D of the paper checks model bugs related to wrong activation function. DeepLocalize produces a single message of the form Batch B Layer L : MSG, where B is the batch number wherein the symptom is detected and L and MSG are the same as we described for Neuralint. A bug is deemed detected if it is located in the layer mentioned in the output message or the message describes any of the root causes of the bug. 2) DeepLocalize: A tool similar to DeepLocalize, but with more bug pattern rules and a decision procedure to give actionable fix suggestions to the users based on the observations. All 8 rules in Table 2 of the paper monitor the symptoms of model bugs. Similar to DeepLocalize, DeepDiagnosis produces a single message of the form Batch B Layer L : MSG1 [OR MSG2], where B and L are the same as described in DeepLocalize and MSG1 and MSG2 are two alternative solutions that the tool might suggest to fix the detected problem. A bug is deemed detected if it is located in the layer mentioned in the output message or the message describes any of the root causes of the bug. 3) DeepDiagnosis: : A hybrid, i.e., a combination of static and dynamic, technique that works by applying heuristic static checks on, and injecting dynamic checks in, the program, parameters, model structure, and model behavior. Violated checks raise error flags which are propagated to a web-based interface that uses visualizations, tutorial explanations, and code snippets to help users find and fix detected errors in their code. All three rules described in Section 5.2 of the paper target model bugs. The tool generates outputs of the form [< MSG1 > · · · < MSGm >] ∗ , where m > 0 and MSGi is a description of the problem detected by the tool. A bug is deemed detected if any of the messages match the fix prescribed by the ground-truth. 4) UMLAUT C. Results To answer RQ1, we ran deepmufl (using its five configurations) and four other tools on the 109 bugs in our benchmark. We refer the reader to the repository [36] for the raw data about which bug is detected by which tool, and here we describe the summaries and provide insights. At top-1, deepmufl detects 42, 47, 26, 37, and 53 bugs using its Metallaxis SBI + Type 1, Metallaxis Ochiai + Type 1, Metallaxis SBI + Type 2, Metallaxis Ochiai + Type 2, and MUSE, respectively, configurations. Meanwhile Neuralint, DeepLocalize, DeepDiagnosis, and UMLAUT detect 21, 26, 30, and 25, respectively, bugs. Therefore, as far as the number of bugs detected by each technique is concerned, MUSE configuration of deepmufl is the most effective configuration of deepmufl, significantly outperforming studied techniques, and Metallaxis Ochiai + Type 2 is the least effective one, outperformed by DeepDiagnosis. An empirical study [57], which uses a specific dataset of traditional buggy programs, concludes that Metallaxis Ochiai + Type 2 is the most effective configuration for MBFL. Meanwhile, our results for DNNs corroborates the theoretical results by Shin and Bae [60], i.e., we provide empirical evidence that in the context of DNNs MUSE is the most effective MBFL approach. Table 3 reports more details and insights on the numbers discussed above. Specifically, it reports the number of bugs detected by each configuration of deepmufl an four other studied tools from each sub-category of model bugs present in our dataset of bugs. As we can see from the upper half of the table, MUSE is most effective in detecting bugs related to activation function (SC1), bugs related to model type/properties (SC2), and wrong/redundant/missing layer (SC4), while Metallaxis Ochiai + Type 1 configuration outperforms other configurations in detecting bugs related to layer properties (SC3). Similarly, from bottom half of the table, we can see that other tools are also quite effective in detecting bugs related to activation function, with DeepDiagnosis being the most effective one among others. We can also observe that UMLAUT has been the most effective tool in detecting bugs related to layer properties. As we can see, MUSE configuration of deepmufl is consistently more effective than other tools across all bug sub-categories. Table 4 provides further insights on the overlap of bugs detected by each variant of deepmufl and those detected by the other four tools. Each value in row r and column c of this table, where 2 ≤ r ≤ 5 and 2 ≤ c ≤ 6, denotes the percentage of bugs detected by the deepmufl variant corresponding to row r and tool corresponding to column c. The values inside the parenthesis are the actual number of bugs. For example, 8 out of 42, i.e., 19.05%, of the bugs detected by Metallaxis SBI + Type 1 configuration of deepmufl are also detected by DeepLocalize. The last column of the table reports same statistics, except for all four of the studied tools combined. As we can see from the table, 60.38% of the bugs detected by MUSE configuration of deepmufl are already detected by one of the four tools, yet it detects 21 (=53-32) bugs that are not detected by any other tools. This is because deepmufl approaches fault localization problem from a fundamentally different aspect giving it more flexibility. Specifically, instead of looking for conditions that trigger a set of hard-coded rules, indicating bug patterns, deepmufl breaks the model using a set of mutators to observe how different mutation impact the model behavior. Then by leveraging the heuristics underlying traditional MBFL techniques, it performs fault localization using the observed impacts on the model behavior. Listing 2 shows an example of a model bug that only deepmufl can detect. The problem with this regression model is that it does not output negative values, and given the fact that the dataset contains negative target values, the model achieves high MSE. Since this model does not result in any numerical errors during training, DeepLocalize does not issue any warning messages, and since MSE decreases and the model does not show any sign of erratic behavior DeepDiagnosis does not detect the bug. UMLAUT’s messages instruct adding softmax layer and checking validation accuracy which is clearly not related to the problem, because the bug is fixed by changing the activation function of the last layer to tanh and normalizing the output values. Lastly, Neuralint issues an error message regarding incorrect loss function which also seems to be a false positive. To answer RQ2, we ran deepmufl and the other four tools on a Dell workstation with Intel(R) Xeon(R) Gold 6138 CPU at 2.00 GHz, 330 GB RAM, 128 GB RAM disk, and Ubuntu 18.04.1 LTS and measured the time needed for model training as well as the MBFL process to complete. We repeated this process four times, and in each round of deepmufl’s execution, we randomly selected 100% (i.e., no selection), 75%, 50%, and 25% of the generated mutants for testing. Random mutation selection is a common method for reducing the overhead of mutation analysis [61], [35]. During random selection, we made sure that each layer receives at least one mutants, so that we do not mask any bug. The last row in Table 5 reports the average timing (of 3 runs) of MBFL in each round of mutation selection. The table also reports the impact of mutation selection on the number of bugs detected by each configuration of deepmufl. As we can see, in MUSE configuration of deepmufl, by using 50% of the mutants, one can halve the execution time and still detect 92.45% of the previously detected bugs. Therefore, mutation selection can be used as an effective way for curtailing MBFL time in DNNs. For a fair comparison of deepmufl to state-of-the-art fault localization tools in terms of efficiency, we need to take into account the fact that deepmufl requires a pre-trained model as its input. Thus, as far as the end-to-end fault localization time from an end-user’s perspective is concerned, we want to take into consideration the time needed to train the input model in addition the time needed to run deepmufl. With training time taken into account, deepmufl takes, on average, 1492.48, 1714.63, 1958.35, and 2192.4 seconds when we select 25%, 50%, 75%, and 100% of the generated mutants, respectively. We also emphasize that the time for DeepLocalize and DeepDiagnosis varied based on whether or not they found the bug. Given the fact that a user could terminate the fault localization process after a few epochs when they lose hope in finding bugs with these two tools, we report two average measurements for DeepLocalize and DeepDiagnosis: (1) average time irrespective of the fact that the tools succeed in finding the bug; (2) average time if the tools successfully finds the bug. Unlike these two tools, the time for Neuralint and UMLAUT does not change based on the fact that they detect a bug or not. DeepLocalize takes on average 1244.09 seconds and it takes on average 57.29 seconds when the tool successfully finds the bug. These numbers for DeepDiagnosis are 1510.71 and 11.05 seconds, respectively. Meanwhile, Neuralint and UMLAUT take on average 2.87 seconds and 1302.61 seconds to perform fault localization. D. Discussion It is important to note that while deepmufl outperforms state-of-the-art techniques in terms of the number of bugs detected in our dataset, it is not meant to replace them. Our dataset only covers a specific type of bugs, i.e., model bugs, while other studied techniques push the envelope by detecting bugs related to factors like learning rate and training data normalization, which are currently outside of deepmufl’s reach. We observed that combining all the techniques results in detecting 87 of the bugs in our dataset; exploring ways to combine various fault localization approaches by picking the right tool based on the characteristics of the bug is an interesting topic for future research. Moreover, depending on the applications and resource constraints, a user might prefer one tool over another. For example, although Neuralint might be limited by its static nature, e.g., it might not be able analyze models that use complex computed values and objects in their construction, it takes only few seconds for the tool to conduct fault localization. Thus, in some applications, e.g., online integration with IDEs, approaches like that of Neuralint might be the best choice A major source of overhead in an MBFL technique is related to the sheer number of mutants that the technique generates and tests [62], [61]. Sufficient mutator selection [63] is referred to the process of selecting a subset of mutators that achieve the same (or similar) effect, i.e., same or similar mutation score and same or similar number of detected bugs, but with smaller number of mutants generated and tested. For the mutators of Table 2, so far, we have not conducted any analysis on which mutators might be redundant, as a reliable mutator selection requires a larger dataset that we currently lack. We postpone this study as a future work. Combining fault localization tools can be conducted with the goal of improving efficiency. We see the opportunity in building faster, yet more effective, fault localization tools by predicting the likely right tool upfront for a given model or running tools one by one and moving on to the next tool if we have a level of confidence that the tool will not find the bug. We postpone this study for a future work. Lastly, we would like to emphasize that comparisons to the above-mentioned techniques in a dataset of bugs that deepmufl supports is fair, as the other tools are also designed to detect bugs in the category of model bugs. However, making these tools to perform better than this, would require augmenting their current rule-base with numerous new rules, yet adding new rules comes with the obligation of justifying the generality and rationale behind them, which might be a quite difficult undertaking. deepmufl, on the other hand, approaches the fault localization problem differently, allowing for more flexibility without the need for hard-coded rules.

Stories, News & Mentions about MUTATA

Mutata’s Stories on HackerNoon