Publications

State aggregations in Markov chains and block models of networks

Faccin, Schaub, Delvenne
arxiv:2005.00337, (2020) ArXiv
Abstract We consider state aggregation schemes for Markov chains from an information-theoretic perspective. Specifically, we consider aggregating the states of a Markov chain such that the mutual information of the aggregated states separated by T time steps is maximized. We show that for T = 1 this approach recovers the maximum-likelihood estimator of the degree-corrected stochastic block model as a particular case, thereby enabling us to explain certain features of the likelihood landscape of this popular generative network model from a dynamical lens. We further highlight how we can uncover coherent, long-range dynamical modules for which considering a time-scale T >> 1 is essential, using synthetic flows and real-world ocean currents, where we are able to recover the fundamental features of the surface currents of the Oceans.
BibTeX
                
@article{faccin2020aggregation,
    author: {Faccin, Mauro and Schaub, Michael T. and Delvenne, Jean-Charles},
    title: {State aggregations in {M}arkov chains and block models of networks},
    eprint: {2005.00337},
    eprinttype: {arxiv},
    archiveprefix: {arXiv},
    primaryclass: {physics.soc-ph},
    year: {2020},
    month: {May},
    url: {http://arxiv.org/abs/2005.00337},
}
                
            

Complex networks from classical to quantum

Biamonte, Faccin, De Domenico
Commun Phys, 2(1) p.53 (2019) ArXiv
Abstract Recent progress in applying complex network theory to problems faced in quantum information and computation has resulted in a beneficial crossover between two fields. Complex network methods have successfully been used to characterize quantum walk and transport models, entangled communication networks, graph theoretic models of emergent space-time and in detecting community structure in quantum systems. Information physics is setting the stage for a theory of complex and networked systems with quantum information-inspired methods appearing in complex network science, including information-theoretic distance and correlation measures for network characterization. Novel quantum induced effects have been predicted in random graphs---where edges represent entangled links---and quantum computer algorithms have recently been proposed to offer super-polynomial enhancement for several network and graph theoretic problems. Here we review the results at the cutting edge, pinpointing the similarities and reconciling the differences found in the series of results at the intersection of these two fields.
BibTeX
                
@article{biamonte2019classicalquantum,
    author: {Biamonte, Jacob and Faccin, Mauro and De Domenico, Manlio},
    title: {Complex networks from classical to quantum},
    journal: {Commun Phys},
    volume: {2},
    version: {1},
    year: {2019},
    pages: {53},
    urldate: {2019-05-21},
    eprinttype: {arxiv},
    eprint: {1702.08459},
    url: {https://doi.org/10.1038/s42005-019-0152-6},
    doi: {10.1038/s42005-019-0152-6},
    number: {1},
    source: {Crossref},
    publisher: {Springer Science and Business Media LLC},
    issn: {2399-3650},
    month: {May},
}
                
            

Entrograms and coarse graining of dynamics on complex networks

Faccin, Schaub, Delvenne
J. Complex Networks, 6(5) p.661-678 (2018) ArXiv
Abstract Using an information theoretic point of view, we investigate how a dynamics acting on a network can be coarse grained through the use of graph partitions. Specifically, we are interested in how aggregating the state space of a Markov process according to a partition impacts on the thus obtained lower-dimensional dynamics. We highlight that for a dynamics on a particular graph there may be multiple coarse grained descriptions that capture different, incomparable features of the original process. For instance, a coarse graining induced by one partition may be commensurate with a time-scale separation in the dynamics, while another coarse graining may correspond to a different lower-dimensional dynamics that preserves the Markov property of the original process. Taking inspiration from the literature of Computational Mechanics, we find that a convenient tool to summarize and visualize such dynamical properties of a coarse grained model (partition) is the entrogram. The entrogram gathers certain information-theoretic measures, which quantify how information flows across time steps. These information theoretic quantities include the entropy rate, as well as a measure for the memory contained in the process, i.e., how well the dynamics can be approximated by a first order Markov process. We use the entrogram to investigate how specific macro-scale connection patterns in the state--space transition graph of the original dynamics result in desirable properties of coarse grained descriptions. We thereby provide a fresh perspective on the interplay between structure and dynamics in networks, and the process of partitioning a network from an information theoretic perspective. To illustrate our points, we focus on networks that may be approximated by both a core-periphery or a clustered organization, and highlight that each of these coarse grained descriptions can capture different aspects of a Markov process acting on the network.
BibTeX
                
@article{faccin2017entrograms,
    author: {Faccin, Mauro and Schaub, Michael T and Delvenne, Jean-Charles},
    title: {Entrograms and coarse graining of dynamics on complex networks},
    journal: {J. Complex Networks},
    volume: {6},
    number: {5},
    pages: {661-678},
    year: {2018},
    doi: {10.1093/comnet/cnx055},
    eprint: {1711.01987},
    eprinttype: {arxiv},
    archiveprefix: {arXiv},
    primaryclass: {soc-ph},
}
                
            

Outbreak of multidrug-resistant tuberculosis in South Africa undetected by WHO-endorsed commercial tests: An observational study

Makhado, Matabane, Faccin, Pinçon, Jouet, Boutachkourt, Goeminne, Gaudin, Maphalala, Beckert, Niemann, Delvenne, Delmée, Razwiedani, Nchabeleng, Supply, de Jong, André
The Lancet Infectious Diseases, 18(12)(12) p.1350-1359 (2018)
Abstract Background Global roll-out of rapid molecular assays is revolutionising the diagnosis of rifampicin resistance, predictive of multidrug-resistance, in tuberculosis. However, 30% of the multidrug-resistant (MDR) strains in an eSwatini study harboured the Ile491Phe mutation in the rpoB gene, which is associated with poor rifampicin-based treatment outcomes but is missed by commercial molecular assays or scored as susceptible by phenotypic drug-susceptibility testing deployed in South Africa. We evaluated the presence of Ile491Phe among South African tuberculosis isolates reported as isoniazid-monoresistant according to current national testing algorithms. Methods We screened records of 37644 Mycobacterium tuberculosis positive cultures from four South African provinces, diagnosed at the National Health Laboratory Service–Dr George Mukhari Tertiary Laboratory, to identify isolates with rifampicin sensitivity and isoniazid resistance according to Xpert MTB/RIF, GenoType MTBDRplus, and BACTEC MGIT 960. Of 1823 isolates that met these criteria, 277 were randomly selected and screened for Ile491Phe with multiplex allele-specific PCR and Sanger sequencing of rpoB. Ile491Phe-positive strains (as well as 17 Ile491Phe-bearing isolates from the eSwatini study) were then tested by Deeplex-MycTB deep sequencing and whole-genome sequencing to evaluate their patterns of extensive resistance, transmission, and evolution. Findings Ile491Phe was identified in 37 (15%) of 249 samples with valid multiplex allele-specific PCR and sequencing results, thus reclassifying them as MDR. All 37 isolates were additionally identified as genotypically resistant to all first-line drugs by Deeplex-MycTB. Six of the South African isolates harboured four distinct mutations potentially associated with decreased bedaquiline sensitivity. Consistent with Deeplex-MycTB genotypic profiles, whole-genome sequencing revealed concurrent silent spread in South Africa of a MDR tuberculosis strain lineage extending from the eSwatini outbreak and at least another independently emerged Ile491Phe-bearing lineage. Whole-genome sequencing further suggested acquisition of mechanisms compensating for the Ile491Phe fitness cost, and of additional bedaquiline resistance following the introduction of this drug in South Africa. Interpretation A substantial number of MDR tuberculosis cases harbouring the Ile491Phe mutation in the rpoB gene in South Africa are missed by current diagnostic strategies, resulting in ineffective first-line treatment, continued amplification of drug resistance, and concurrent silent spread in the community.
BibTeX
                
@article{makhado2018outbreakdrugresistant,
    author: {Makhado, Ndivhuho A and Matabane, Edith and Faccin, Mauro and Pinçon, Claire and Jouet, Agathe and Boutachkourt, Fairouz and Goeminne, Léonie and Gaudin, Cyril and Maphalala, Gugu and Beckert, Patrick and Niemann, Stefan and Delvenne, Jean-Charles and Delmée, Michel and Razwiedani, Lufuno and Nchabeleng, Maphoshane and Supply, Philip and de Jong, Bouke C and André, Emmanuel},
    title: {Outbreak of multidrug-resistant tuberculosis in {S}outh {A}frica undetected by {WHO}-endorsed commercial tests: {A}n observational study},
    journal: {The Lancet Infectious Diseases},
    year: {2018},
    issn: {1473-3099},
    volume: {18},
    issue: {12},
    pages: {1350-1359},
    doi: {10.1016/s1473-3099(18)30496-1},
    url: {https://doi.org/10.1016/s1473-3099(18)30496-1},
    number: {12},
    source: {Crossref},
    publisher: {Elsevier BV},
    month: {December},
}
                
            

Chiral quantum walks

Lu, Biamonte, Li, Li, Johnson, Bergholm, Faccin, Zimborás, Laflamme, Baugh, Lloyd
Phys. Rev. A, 93(4) p.042302 (2016) ArXiv
Abstract Wigner separated the possible types of symmetries in quantum theory into those symmetries that are unitary and those that are antiunitary. Unitary symmetries have been well studied whereas antiunitary symmetries and the physical implications associated with time-reversal symmetry breaking have had little influence on quantum information science. Here we develop a quantum circuits version of time-reversal symmetry theory, classifying time-symmetric and time-asymmetric Hamiltonians and circuits in terms of their underlying network elements and geometric structures. These results reveal that many of the typical quantum circuit networks found across the field of quantum information science exhibit time-asymmetry. We then experimentally implement the most fundamental time-reversal asymmetric process, applying local gates in an otherwise time-symmetric circuit to induce time-reversal asymmetry and thereby achieve (i) directional biasing in the transition probability between basis states, (ii) the enhancement of and (iii) the suppression of these transport probabilities. Our results imply that the physical effect of time-symmetry breaking plays an essential role in coherent transport and its control represents an omnipresent yet essentially untapped resource in quantum transport science.
BibTeX
                
@article{lu2014chiral,
    author: {Lu, Dawei and Biamonte, Jacob D. and Li, Jun and Li, Hang and Johnson, Tomi H. and Bergholm, Ville and Faccin, Mauro and Zimborás, Zoltán and Laflamme, Raymond and Baugh, Jonathan and Lloyd, Seth},
    title: {Chiral quantum walks},
    journal: {Phys. Rev. A},
    volume: {93},
    issue: {4},
    pages: {042302},
    numpages: {7},
    year: {2016},
    month: {April},
    publisher: {American Physical Society},
    doi: {10.1103/PhysRevA.93.042302},
    url: {http://link.aps.org/doi/10.1103/PhysRevA.93.042302},
    eprinttype: {arxiv},
    eprint: {1405.6209},
    primaryclass: {quant-ph},
}
                
            

Mapping the Topography of a Protein Energy Landscape

Hutton, Wilkinson, Faccin, Sivertsson, Pelizzola, Lowe, Bruscolini, Itzhaki
J. Am. Chem. Soc., 137(46) p.14610-14625 (2015)
Abstract Protein energy landscapes are highly complex, yet the vast majority of states within them tend to be invisible to experimentalists. Here, using site-directed mutagenesis and exploiting the simplicity of tandem-repeat protein structures, we delineate a network of these states and the routes between them. We show that our target, gankyrin, a 226-residue 7-ankyrin-repeat protein, can access two alternative (un)folding pathways. We resolve intermediates as well as transition states, constituting a comprehensive series of snapshots that map early and late stages of the two pathways and show both to be polarized such that the repeat array progressively unravels from one end of the molecule or the other. Strikingly, we find that the protein folds via one pathway but unfolds via a different one. The origins of this behavior can be rationalized using the numerical results of a simple statistical mechanics model that allows us to visualize the equilibrium behavior as well as single-molecule folding/unfolding trajectories, thereby filling in the gaps that are not accessible to direct experimental observation. Our study highlights the complexity of repeat-protein folding arising from their symmetrical structures; at the same time, however, this structural simplicity enables us to dissect the complexity and thereby map the precise topography of the energy landscape in full breadth and remarkable detail. That we can recapitulate the key features of the folding mechanism by computational analysis of the native structure alone will help toward the ultimate goal of designed amino-acid sequences with made-to-measure folding mechanisms---the Holy Grail of protein folding.
BibTeX
                
@article{hutton2015gankyrin,
    author: {Hutton, Richard D. and Wilkinson, James and Faccin, Mauro and Sivertsson, Elin M. and Pelizzola, Alessandro and Lowe, Alan R. and Bruscolini, Pierpaolo and Itzhaki, Laura S.},
    title: {Mapping the Topography of a Protein Energy Landscape},
    journal: {J. Am. Chem. Soc.},
    volume: {137},
    number: {46},
    pages: {14610-14625},
    year: {2015},
    doi: {10.1021/jacs.5b07370},
    note: {PMID: 26561984},
    url: {https://doi.org/10.1021/jacs.5b07370},
    eprint: {http://dx.doi.org/10.1021/jacs.5b07370},
}
                
            

Community Detection in Quantum Complex Networks

Faccin, Migdał, Johnson, Bergholm, Biamonte
Phys. Rev. X, 4(4) p.041012 (2014) ArXiv
Abstract Determining community structure is a central topic in the study of complex networks, be it technological, social, biological or chemical, static or in interacting systems. In this paper, we extend the concept of community detection from classical to quantum systems---a crucial missing component of a theory of complex networks based on quantum mechanics. We demonstrate that certain quantum mechanical effects cannot be captured using current classical complex network tools and provide new methods that overcome these problems. Our approaches are based on defining closeness measures between nodes, and then maximizing modularity with hierarchical clustering. Our closeness functions are based on quantum transport probability and state fidelity, two important quantities in quantum information theory. To illustrate the effectiveness of our approach in detecting community structure in quantum systems, we provide several examples, including a naturally occurring light-harvesting complex, LHCII. The prediction of our simplest algorithm, semiclassical in nature, mostly agrees with a proposed partitioning for the LHCII found in quantum chemistry literature, whereas our fully quantum treatment of the problem uncovers a new, consistent, and appropriately quantum community structure.
BibTeX
                
@article{faccin2014community,
    author: {Faccin, Mauro and Migdał, Piotr and Johnson, Tomi H. and Bergholm, Ville and Biamonte, Jacob D.},
    title: {Community Detection in Quantum Complex Networks},
    journal: {Phys. Rev. X},
    volume: {4},
    issue: {4},
    pages: {041012},
    numpages: {11},
    year: {2014},
    month: {October},
    publisher: {American Physical Society},
    doi: {10.1103/PhysRevX.4.041012},
    url: {http://link.aps.org/doi/10.1103/PhysRevX.4.041012},
    eprinttype: {arxiv},
    eprint: {1310.6638},
    primaryclass: {quant-ph},
}
                
            

Degree Distribution in Quantum Walks on Complex Networks

Faccin, Johnson, Biamonte, Kais, Migdał
Phys. Rev. X, 3(4) p.041007 (2013) ArXiv
Abstract In this theoretical study, we analyze quantum walks on complex networks, which model network-based processes ranging from quantum computing to biology and even sociology. Specifically, we analytically relate the average long-time probability distribution for the location of a unitary quantum walker to that of a corresponding classical walker. The distribution of the classical walker is proportional to the distribution of degrees, which measures the connectivity of the network nodes and underlies many methods for analyzing classical networks, including website ranking. The quantum distribution becomes exactly equal to the classical distribution when the walk has zero energy, and at higher energies, the difference, the so-called quantumness, is bounded by the energy of the initial state. We give an example for which the quantumness equals a R'enyi entropy of the normalized weighted degrees, guiding us to regimes for which the classical degree-dependent result is recovered and others for which quantum effects dominate.
BibTeX
                
@article{faccin2013degree,
    author: {Faccin, Mauro and Johnson, Tomi and Biamonte, Jacob and Kais, Sabre and Migdał, Piotr},
    title: {Degree Distribution in Quantum Walks on Complex Networks},
    journal: {Phys. Rev. X},
    volume: {3},
    issue: {4},
    pages: {041007},
    numpages: {8},
    year: {2013},
    month: {October},
    doi: {10.1103/PhysRevX.3.041007},
    publisher: {American Physical Society},
    impactfactor: {6.71},
    eprinttype: {arxiv},
    eprint: {1305.6078},
    primaryclass: {quant-ph},
}
                
            

Quantum Transport Enhancement by Time-Reversal Symmetry Breaking

Zimborás, Faccin, Kadar, Whitfield, Lanyon, Biamonte
Sci. Rep., 3 p.2361 (2013) ArXiv
Abstract Quantum mechanics still provides new unexpected effects when considering the transport of energy and information. Models of continuous time quantum walks, which implicitly use time-reversal symmetric Hamiltonians, have been intensely used to investigate the effectiveness of transport. Here we show how breaking time-reversal symmetry of the unitary dynamics in this model can enable directional control, enhancement, and suppression of quantum transport. Examples ranging from exciton transport to complex networks are presented. This opens new prospects for more efficient methods to transport energy and information.
BibTeX
                
@article{zimboras2013,
    author: {Zimborás, Zoltán and Faccin, Mauro and Kadar, Zoltán and Whitfield, James and Lanyon, Ben and Biamonte, Jacob},
    editor: {Npg},
    title: {Quantum Transport Enhancement by Time-Reversal Symmetry Breaking},
    journal: {Sci. Rep.},
    volume: {3},
    pages: {2361},
    doi: {10.1038/srep02361},
    year: {2013},
    archiveprefix: {arxiv},
    eprint: {1208.4049},
    eprinttype: {arxiv},
    primaryclass: {quant-ph},
    impactfactor: {2.927},
}
                
            

MS/MS Spectra Interpretation as a Statistical-Mechanics Problem

Faccin, Bruscolini
Anal. Chem., 85(10) p.4884-4892 (2013)
Abstract We describe a new method for peptide sequencing based on the mapping of the interpretation of tandem mass spectra onto the analysis of the equilibrium distribution of a suitably defined physical model, whose variables describe the positions of the fragmentation sites along a discrete mass index. The model is governed by a potential energy function that, at present, we derive ad hoc from the distribution of peaks in a data set of experimental spectra. The statistical--physics perspective prompts for a consistent and unified approach to de novo and database-search methods, which is a distinctive feature of this approach over alternative ones: the characterization of the ground state of the model allows the de novo identification of the precursor peptide; the study of the thermodynamic variables as a function of the (fictitious) temperature gives insight on the quality of the prediction, while the probability profiles at nonzero temperature reveal, on one hand, which fragments are more reliably predicted. On the other hand, they can be used as a spectrum-adapted, a posteriori score for database search. Results obtained with two different test data sets reveal a performance similar to that of other de novo and database-search methods, which is reasonable, given the lack of an aggressive optimization of the energy function at this stage. An important feature of the method is that it is quite general and can be applied with different choices of the energy function: we discuss its possible improvements and generalizations.
BibTeX
                
@article{faccin2013msms,
    author: {Faccin, Mauro and Bruscolini, Pierpaolo},
    title: {{MS/MS} Spectra Interpretation as a Statistical-Mechanics Problem},
    journal: {Anal. Chem.},
    volume: {85},
    number: {10},
    pages: {4884-4892},
    year: {2013},
    doi: {10.1021/ac4005666},
    url: {https://pubs.acs.org/doi/abs/10.1021/ac4005666},
    impactfactor: {5.695},
}
                
            

Ground-state spin logic

Whitfield, Faccin, Biamonte
Europhys. Lett., 99(5) p.57004 (2012) ArXiv
Abstract Designing and optimizing cost functions and energy landscapes is a problem encountered in many fields of science and engineering. These landscapes and cost functions can be embedded and annealed in experimentally controllable spin Hamiltonians. Using an approach based on group theory and symmetries, we examine the embedding of Boolean logic gates into the ground-state subspace of such spin systems. We describe parameterized families of diagonal Hamiltonians and symmetry operations which preserve the ground-state subspace encoding the truth tables of Boolean formulas. The ground-state embeddings of adder circuits are used to illustrate how gates are combined and simplified using symmetry. Our work is relevant for experimental demonstrations of ground-state embeddings found in both classical optimization as well as adiabatic quantum optimization.
BibTeX
                
@article{whitfield2012spinlogic,
    author: {Whitfield, James D. and Faccin, Mauro and Biamonte, Jacob D.},
    title: {Ground-state spin logic},
    journal: {Europhys. Lett.},
    volume: {99},
    number: {5},
    pages: {57004},
    doi: {10.1209/0295-5075/99/57004},
    eprinttype: {arxiv},
    eprint: {1205.1742},
    primaryclass: {quant-ph},
    year: {2012},
    impactfactor: {2.260},
}
                
            

Analysis of the equilibrium and kinetics of the ankyrin repeat protein myotrophin

Faccin, Bruscolini, Pelizzola
The Journal of Chemical Physics, 134(7) p.075102 (2011) ArXiv
Abstract We apply the Wako-Saito-Mu~noz-Eaton model to the study of myotrophin, a small ankyrin repeat protein, whose folding equilibrium and kinetics have been recently characterized experimentally. The model, which is a native-centric with binary variables, provides a finer microscopic detail than the Ising model that has been recently applied to some different repeat proteins, while being still amenable for an exact solution. In partial agreement with the experiments, our results reveal a weakly three-state equilibrium and a two-state-like kinetics of the wild-type protein despite the presence of a nontrivial free-energy profile. These features appear to be related to a careful ``design'' of the free-energy landscape, so that mutations can alter this picture, stabilizing some intermediates and changing the position of the rate-limiting step. Also, the experimental findings of two alternative pathways, an N-terminal and a C-terminal one, are qualitatively confirmed, even if the variations in the rates upon the experimental mutations cannot be quantitatively reproduced. Interestingly, the folding and unfolding pathways appear to be different, even if closely related: a property that is not generally considered in the phenomenological interpretation of the experimental data.
BibTeX
                
@article{faccin2011ankyrin,
    author: {Faccin, Mauro and Bruscolini, Pierpaolo and Pelizzola, Alessandro},
    title: {Analysis of the equilibrium and kinetics of the ankyrin repeat protein myotrophin},
    publisher: {AIP},
    year: {2011},
    journal: {The Journal of Chemical Physics},
    volume: {134},
    number: {7},
    eid: {075102},
    numpages: {11},
    pages: {075102},
    keywords: {biochemistry; chemical equilibrium; free energy; molecular biophysics; proteins; reaction kinetics theory},
    doi: {10.1063/1.3535562},
    eprinttype: {arxiv},
    eprint: {1103.0216},
    impactfactor: {3.164},
}