bioinformatics tool developers

Abstract: Protein-protein interaction databases record evidence without weighing it. In BioGRID, an interaction asserted once by a single high-throughput screen and one confirmed by twenty laboratories across a dozen assays are the same kind of row in the same file. Tools built on such databases inherit that flattening: they draw every reported interaction as an edge, and the resulting picture states that two proteins interact without stating how much anyone should believe it. We present ProLiVis 2.0, a rewrite of the literature-centric visualization system of arXiv:2111.12794. It contributes three things. First, a citation-trust model that scores each interaction from seven terms, including a term for the number of independent laboratories behind the supporting publications, obtained by clustering those publications over shared institutional affiliations; a plain count of publications cannot distinguish five confirmations from one group publishing five times. Second, a deterministic reformulation of the center layout, closed-form and $O(n \log n)$, which replaces the force-directed placement of the original and makes published figures regenerable from a session manifest. Third, an implementation that runs entirely in a web browser, with an embedded analytical database, requiring no installation and uploading no data. On BioGRID release 5.0.260 restricted to SARS-CoV-2, 24,344 of 34,540 reported interactions (70%) rest on a single publication, and raising the trust threshold to 0.2 leaves 11,320 of them. That the large majority of a curated interaction network is unreplicated is a fact no existing view of the database makes visible.

Abstract: We study the weighted feedback vertex set problem in tournaments. For every fixed integer $k\geq 2$, we give a deterministic $(2+1/k)$-approximation algorithm with running time $n^{2^{O(k)}}$, apart from polynomial dependence on the encoding length of the weights. Consequently, for every fixed $\varepsilon>0$, weighted feedback vertex set in tournaments has a deterministic $(2+\varepsilon)$-approximation running in time $n^{2^{O(1/\varepsilon)}}$. The algorithm combines two ingredients. When the triangle graph of the tournament has bounded clique number, a chain decomposition of its transitive complement yields an exact dynamic program for a maximum-weight transitive subtournament. When the clique number is large, a structural theorem for triangle graphs supplies a constant-size strongly good cost vector. A local-ratio reduction with this cost vector gives the claimed guarantee. As a by-product, the dynamic program solves weighted feedback vertex set exactly in $\mathcal B_7$-free tournaments in time $O(n^7)$, where $\mathcal B_7$ is the family of seven-vertex tournaments with feedback vertex set number at least three.