11 research outputs found
Combinatorial aspects of low-rank matrix factorization and two applications in bioinformatics
No full textFritzilas E. Combinatorial aspects of low-rank matrix factorization and two applications in bioinformatics. Bielefeld (Germany): Bielefeld University; 2009.In many signal processing and data mining applications we need to write a given matrix Y as a low-rank product Y = AX. Both matrices A and X have to be determined and we assume that from the specifics of the application we can derive some constraints for A and X. In general, there are different factorizations that approximate a given Y equally well and, therefore, the problem is inherently ill-defined. On the other hand, we intuitively expect that the constraints that we impose on the factors must offer some control over the space of possible solutions.
In this work, we focus on an especially strong class of constraints. They arise in applications that involve a bipartite network of sources that are emitting some signals over discrete time and sensors that are monitoring these signals. In this context, Y contains sensor measurements over several time points, X contains source signals over time points and A contains the source-sensor mixing coefficients. We assume that we know a-priori the connectivity of the network, which implies that, in the factorization Y = AX, A (the matrix of the mixing coefficients) must have zeros at certain positions. For this class of constraints a fundamental question arises: Does the known zero pattern of A contribute anything to the uniqueness of the factorization?
An observation that follows from the linearity of the model naturally leads us to a characterization of uniqueness up to diagonal scaling. It is important to note that this characterization is combinatorial, in the sense that it is based solely on the structure of the source-sensor network and not on the numerical values of a particular (A,X) solution. In fact, it only assumes that the matrices A and X of a solution are numerically generic. This discussion is formalized in Chapter 3 with the definition of identifiable bipartite graphs. Thereby, the concept of structural rank is the crucial link between linear algebra and graph theory.
Identifiable graphs are defined in terms of bipartite matchings, which are very well-studied objects both in graph theory and in computer science. Below we mention some classical results that we use in our investigations. We can only start with Hall's marriage theorem, which gives a concise theoretical characterization for the existence of perfect matchings in bipartite graphs. From the algorithmic point of view, a maximum matching can be efficiently computed due to Berge's theorem and the concept of augmenting paths. An elegant connection of bipartite matchings to linear programming via totally unimodular matrices builds a bridge between continuous and combinatorial optimization. In the case of non-identifiable graphs, we draw some conclusions about the identifiability of the model, using the Dulmage-Mendelsohn (DM) decomposition of bipartite graphs. Finally, the concepts of surplus and submodular set functions appear at different points of the discussion.
After the definition of identifiable graphs, we focus on two optimization problems that arise in the context of source-sensor networks. For these problems we coin the names MINSENSOR and MINSOURCE; we define and study them in Chapters 4 and 5, respectively. Roughly speaking, both problems deal with the selection of good subgraphs: Given a bipartite graph G the goal is to find a subgraph of G that is identifiable and also satisfies some additional restrictions. Both problems turn out to be NP-hard, as we show with reductions from SET COVER. This is a prototypical NP-hard problem with many generalizations, for many of which the approximation (and inapproximability) properties have been well-studied. One powerful generalization is SUBMODULAR SET COVER, for which a greedy approach achieves a logarithmic approximation guarantee. We derive an approximation algorithm for MINSENSOR by showing that it is a special case of SUBMODULAR SET COVER.
In Chapter 6 we ask another natural question that arises from our need to model uncertainty in the network structure. Given an identifiable graph G, where the edges have been predicted with some uncertainty, how many edge modifications does it take, so that G loses the property? This robustness question is reduced to the computation of surplus in bipartite graphs and we show how this can be done in polynomial time.
In Chapters 7 and 8 we present two applications from bioinformatics that can be abstracted in the context of a source-sensor network. The first one is dealing with the processing of microarray data under the presence of non-specific probes and the second one is dealing with the quantification of transcription factor activities in simple regulatory networks.
To the best of our knowledge we are the first to define identifiable bipartite graphs in order to study the uniqueness of solutions in low-rank matrix factorization. We are also the first to investigate the properties of these graphs and related combinatorial optimization problems that arise in the context of source-sensor networks
Structural Identifiability in Low-Rank Matrix Factorization
No full textFritzilas E, Rios-Solis YA, Rahmann S. Structural Identifiability in Low-Rank Matrix Factorization. In: Hu X, Wang J, eds. Computing and Combinatorics 14th Annual International Conference, COCOON 2008 Dalian, China, June 27-29, 2008 Proceedings. Lecture Notes in Computer Science, 5092. Berlin u.a.: Springer; 2008: 140-148
Kombinatorische Aspekte der Matrixfaktorisierung und verwandte Probleme aus der Signalverarbeitung
No full textResilience and optimization of identifiable bipartite graphs
No full textInternational audienceA bipartite graph G=(L,R;E) with at least one edge is said to be identifiable if for every vertex v∈L, the subgraph induced by its non-neighbors has a matching of cardinality |L|−1. This definition arises in the context of low-rank matrix factorization and is motivated by signal processing applications.In this paper, we study the resilience of identifiability with respect to edge additions, edge deletions and edge modifications. These can all be seen as measures of evaluating how strongly a bipartite graph possesses the identifiability property. On the one hand, we show that computing the resilience of this non-monotone property can be done in polynomial time for edge additions or edge modifications. On the other hand, for edge deletions this is an NP-complete problem. Our polynomial results are based on polynomial algorithms for computing the surplus of a bipartite graph G and finding a tight set in G, which might be of independent interest.We also deal with some complexity results for the optimization problem related to the isolation of a smallest set J⊆L that, together with all vertices with neighbors only in J, induces an identifiable subgraph. We obtain an APX-hardness result for the problem and identify some polynomially solvable cases
A matching-related property of bipartite graphs with applications in signal processing
No full textA bipartite graph G = (L,R;E) is said to be identifiable if for every vertex v ∈ L,
the subgraph induced by its non-neighbors has a matching of cardinality |L| − 1.
This definition arises in the context of low-rank matrix factorization. Motivated by
signal processing applications, in this paper we (i) propose the robustness of identifiability
with respect to edge modifications as a polynomially computable measure
of evaluating how strongly a bipartite graph possesses the property of identifiability,
and (ii) introduce three problems that deal with finding identifiable subgraphs, and
study their complexity.ou
Modeling cross-hybridization on phylogenetic DNA microarrays increases the detection power of closely related species
No full textEngelmann JA, Rahmann S, Wolf M, et al. Modeling cross-hybridization on phylogenetic DNA microarrays increases the detection power of closely related species. Molecular Ecology Resources. 2009;9(1):83-93
Massive parallel bisulfite sequencing of CG-rich DNA fragments reveals that methylation of many X-chromosomal CpG islands in female blood DNA is incomplete
No full textZeschnigk M, Martin M, Betzl G, et al. Massive parallel bisulfite sequencing of CG-rich DNA fragments reveals that methylation of many X-chromosomal CpG islands in female blood DNA is incomplete. HUMAN MOLECULAR GENETICS. 2009;18(8):1439-1448.Methylation of CpG islands (CGIs) plays an important role in gene silencing. For genome-wide methylation analysis of CGIs in female white blood cells and in sperm, we used four restriction enzymes and a size selection step to prepare DNA libraries enriched with CGIs. The DNA libraries were treated with sodium bisulfite and subjected to a modified 454/Roche Genome Sequencer protocol. We obtained 163 034 and 129 620 reads from blood and sperm, respectively, with an average read length of 133 bp. Bioinformatic analysis revealed that 12 358 (7.6%) blood library reads and 10 216 (7.9%) sperm library reads map to 6167 and 5796 different CGIs, respectively. In blood and sperm DNA, we identified 824 (13.7%) and 482 (8.5%) fully methylated autosomal CGIs, respectively. Differential methylation, which is characterized by the presence of methylated and unmethylated reads of the same CGI, was observed in 53 and 52 autosomal CGIs in blood and sperm DNA, respectively. Remarkably, methylation of X-chromosomal CGIs in female blood cells was most often incomplete (25-75%). Such incomplete methylation was mainly found on the X-chromosome, suggesting that it is linked to X-chromosome inactivation
Author Correction: Predicting the clinical impact of human mutation with deep neural networks
No full textA reference data set of 5.4 million phased human variants validated by genetic inheritance from sequencing a three-generation 17-member pedigree.
No full textImprovement of variant calling in next-generation sequence data requires a comprehensive, genome-wide catalog of highconfidence variants called in a set of genomes for use as a benchmark. We generated deep, whole-genome sequence data of 17 individuals in a three-generation pedigree and called variants in each genome using a range of currently available algorithms. We used haplotype transmission information to create a phased“Platinum”variant catalog of 4.7 million singlenucleotide variants (SNVs) plus 0.7 million small (1–50 bp) insertions and deletions (indels) that are consistent with the pattern of inheritance in the parents and 11 children of this pedigree. Platinum genotypes are highly concordant with the current catalog of the National Institute of Standards and Technology for both SNVs (>99.99%) and indels (99.92%) and add a validated truth catalog that has 26% more SNVs and 45% more indels. Analysis of 334,652 SNVs that were consistent between informatics pipelines yet inconsistent with haplotype transmission (“nonplatinum”) revealed that the majority of these variants are de novo and cell-line mutations or reside within previously unidentified duplications and deletions. The reference materials from this study are a resource for objective assessment of the accuracy of variant calls throughout genomes
