The protein inference problem, i.e., determining which proteins are present in a biological sample, is key to understanding the roles of proteins and, more broadly, many biological processes. Protein identification is typically achieved by first cleaving proteins into smaller sequences called peptides. Peptides are then identified using tandem mass spectrometry, a process that produces mass spectra, and in which peptide identification consists of associating, via dedicated tools, a mass spectrum to a peptide sequence. Protein inference consists of identifying, from a list of identified peptides, the proteins that most likely produced them, and were therefore present in the original sample. Usually, peptide identification and protein inference are two separate steps, which are sequentially achieved. However, by proceeding in such a way, a significant amount of potentially useful information contained in the spectra may be discarded in the second step. Moreover, AI-based tools can now predict the likelihood of a peptide’s identification when its parent protein is present in the sample. In this paper, we present the Global Spectrum Interpretation (GSI) model, a protein inference model that integrates all this information to produce more accurate protein identifications. We show that GSI is NP-hard and provide a Mixed Integer Linear Program (MILP) formulation for it. This MILP is then benchmarked against state-of-the-art protein inference models on several datasets. Our results show that GSI’s promising and original approach achieves performance comparable to current models and outperforms other widely used ones, while being more explainable.

Genome Rearrangement distance problems are used in Computational Biology to estimate the evolutionary distance between genomes. These problems consist of minimizing the number of rearrangement events necessary to transform one genome into another. Two commonly used rearrangement events are reversal and transposition. The first studied problems ignored nucleotides outside genes (called intergenic regions), or assumed that genomes have a single copy of each gene. Recent works made advancements in more general problems considering the number of nucleotides in intergenic regions, and replicated genes. Nevertheless, genomes tend to have wildly different quantities of nucleotides on their intergenic regions, which poses a problem when comparing these regions exactly. To overcome this limitation, our work considers some flexibility when matching intergenic regions that do not have the same number of nucleotides. We propose new problems seeking the minimum number of reversals, or reversals and transpositions, necessary to transform one genome into another, while considering flexible intergenic region information. We show approximations for these problems by exploring their relationship with the Signed Minimum Common Flexible Intergenic String Partition problem. We also present different heuristics for the partition problem, and conduct experimental tests on simulated genomes to assess the performance of our algorithms.

In this paper, we study the problem of sorting unichromosomal linear genomes by prefix double-cut-and-joins (or DCJs) in both the signed and the unsigned settings. Prefix DCJs cut the leftmost segment of a genome and any other segment, and recombine the severed endpoints in one of two possible ways: one of these options corresponds to a prefix reversal, which reverses the order of elements between the two cuts (as well as their signs in the signed case). Our main results are: (1) new structural lower bounds based on the breakpoint graph for sorting by unsigned prefix reversals, unsigned prefix DCJs, and signed prefix DCJs; (2) two polynomial-time algorithms for sorting by prefix DCJs, both in the signed case (which answers an open question of Labarre [1] ) and in the unsigned case; (3) a 1-absolute approximation algorithm for sorting by unsigned prefix reversals for a specific class of permutations.

We study the Maximum Zero-Sum Partition problem (or MZSP ), defined as follows: given a multiset S = { a 1 , a 2 , … , a n } of integers a i ∈ Z ⁎ (where Z ⁎ denotes the set of non-zero integers) such that ∑ i = 1 n a i = 0 , find a maximum cardinality partition { S 1 , S 2 , … , S k } of S such that, for every 1 ≤ i ≤ k , ∑ a j ∈ S i a j = 0 . Solving MZSP is useful in genomics for computing evolutionary distances between pairs of species. Our contributions are a series of algorithmic results concerning MZSP , in terms of complexity, (in)approximability, with a particular focus on the fixed-parameter tractability of MZSP with respect to either (i) the size k of the solution, (ii) the number of negative (resp. positive) values in S and (iii) the largest integer in S .

BACKGROUND: In proteomics, the interpretation of mass spectra representing peptides carrying multiple complex modifications remains challenging, as it is difficult to strike a balance between reasonable execution time, a limited number of false positives, and a huge search space allowing any number of modifications without a priori. The scientific community needs new developments in this area to aid in the discovery of novel post-translational modifications that may play important roles in disease. RESULTS: To make progress on this issue, we implemented SpecGlobX (SpecGlob eXTended to eXperimental spectra), a standalone Java application that quickly determines the best spectral alignments of a (possibly very large) list of Peptide-to-Spectrum Matches (PSMs) provided by any open modification search method, or generated by the user. As input, SpecGlobX reads a file containing spectra in MGF or mzML format and a semicolon-delimited spreadsheet describing the PSMs. SpecGlobX returns the best alignment for each PSM as output, splitting the mass difference between the spectrum and the peptide into one or more shifts while considering the possibility of non-aligned masses (a phenomenon resulting from many situations including neutral losses). SpecGlobX is fast, able to align one million PSMs in about 1.5 min on a standard desktop. Firstly, we remind the foundations of the algorithm and detail how we adapted SpecGlob (the method we previously developed following the same aim, but limited to the interpretation of perfect simulated spectra) to the interpretation of imperfect experimental spectra. Then, we highlight the interest of SpecGlobX as a complementary tool downstream to three open modification search methods on a large simulated spectra dataset. Finally, we ran SpecGlobX on a proteome-wide dataset downloaded from PRIDE to demonstrate that SpecGlobX functions just as well on simulated and experimental spectra. We then carefully analyzed a limited set of interpretations. CONCLUSIONS: SpecGlobX is helpful as a decision support tool, providing keys to interpret peptides carrying complex modifications still poorly considered by current open modification search software. Better alignment of PSMs enhances confidence in the identification of spectra provided by open modification search methods and should improve the interpretation rate of spectra.

We study in this paper the Doubly Partially Ordered Pattern Matching (or DPOP Matching) problem, a natural extension of the Permutation Pattern Matching problem. Permutation Pattern Matching takes as input two permutations σ and π, and asks whether there exists an occurrence of σ in π; whereas DPOP Matching takes two partial orders P_v and P_p defined on the same set X and a permutation π, and asks whether there exist |X| elements in π whose values (resp., positions) are in accordance with P_v (resp., P_p). Posets P_v and P_p aim at relaxing the conditions formerly imposed by the permutation σ, since σ yields a total order on both positions and values. Our problem being NP-hard in general (as Permutation Pattern Matching is), we consider restrictions on several parameters/properties of the input, e.g., bounding the size of the pattern, assuming symmetry of the posets (i.e., P_v and P_p are identical), assuming that one partial order is a total (resp., weak) order, bounding the length of the longest chain/anti-chain in the posets, or forbidding specific patterns in π. For each such restriction, we provide results which together give a(n almost) complete landscape for the algorithmic complexity of the problem.

BACKGROUND: Mass spectrometry remains the privileged method to characterize proteins. Nevertheless, most of the spectra generated by an experiment remain unidentified after their analysis, mostly because of the modifications they carry. Open Modification Search (OMS) methods offer a promising answer to this problem. However, assessing the quality of OMS identifications remains a difficult task. METHODS: Aiming at better understanding the relationship between (1) similarity of pairs of spectra provided by OMS methods and (2) relevance of their corresponding peptide sequences, we used a dataset composed of theoretical spectra only, on which we applied two OMS strategies. We also introduced two appropriately defined measures for evaluating the above mentioned spectra/sequence relevance in this context: one is a color classification representing the level of difficulty to retrieve the proper sequence of the peptide that generated the identified spectrum ; the other, called LIPR, is the proportion of common masses, in a given Peptide Spectrum Match (PSM), that represent dissimilar sequences. These two measures were also considered in conjunction with the False Discovery Rate (FDR). RESULTS: According to our measures, the strategy that selects the best candidate by taking the mass difference between two spectra into account yields better quality results. Besides, although the FDR remains an interesting indicator in OMS methods (as shown by LIPR), it is questionable: indeed, our color classification shows that a non negligible proportion of relevant spectra/sequence interpretations corresponds to PSMs coming from the decoy database. CONCLUSIONS: The three above mentioned measures allowed us to clearly determine which of the two studied OMS strategies outperformed the other, both in terms of number of identifications and of accuracy of these identifications. Even though quality evaluation of PSMs in OMS methods remains challenging, the study of theoretical spectra is a favorable framework for going further in this direction.

Genome rearrangements are mutations affecting large portions of a genome, and a reversal is one of the most studied genome rearrangements in the literature through the Sorting by Reversals (SbR) problem. SbR is solvable in polynomial time on signed permutations (i.e., the gene orientation is known), and it is NP-hard on unsigned permutations. This problem (and many others considering genome rearrangements) models genome as a list of its genes in the order they appear, ignoring all other information present in the genome. Recent works claimed that the incorporation of the size of intergenic regions, i.e., sequences of nucleotides between genes, may result in better estimators for the real distance between genomes. Here we introduce the Sorting Signed Permutations by Intergenic Reversals problem, that sorts a signed permutation using reversals both on gene order and intergenic sizes. We show that this problem is NP-hard by a reduction from the 3-partition problem. Then, we propose a 2-approximation algorithm for it. Finally, we also incorporate intergenic indels (i.e., insertions or deletions of intergenic regions) to overcome a limitation of sorting by conservative events (such as reversals) and propose two approximation algorithms.

Genome Rearrangements are events that affect large stretches of genomes during evolution. Many mathematical models have been used to estimate the evolutionary distance between two genomes based on genome rearrangements. However, most of them focused on the (order of the) genes of a genome, disregarding other important elements in it. Recently, researchers have shown that considering regions between each pair of genes, called intergenic regions, can enhance distance estimation in realistic data. Two of the most studied genome rearrangements are the reversal, which inverts a sequence of genes, and the transposition, which occurs when two adjacent gene sequences swap their positions inside the genome. In this work, we study the transposition distance between two genomes, but we also consider intergenic regions, a problem we name Sorting by Intergenic Transpositions. We show that this problem is NP-hard and propose two approximation algorithms, with factors 3.5 and 2.5, considering two distinct definitions for the problem. We also investigate the signed reversal and transposition distance between two genomes considering their intergenic regions. This second problem is called Sorting by Signed Intergenic Reversals and Intergenic Transpositions. We show that this problem is NP-hard and develop two approximation algorithms, with factors 3 and 2.5. We check how these algorithms behave when assigning weights for genome rearrangements. Finally, we implemented all these algorithms and tested them on real and simulated data.

A partition $(V_1,\ldots,V_k)$ of the vertex set of a graph $G$ with a (not necessarily proper) colouring $c$ is colourful if no two vertices in any $V_i$ have the same colour and every set $V_i$ induces a connected graph. The COLOURFUL PARTITION problem is to decide whether a coloured graph $(G,c)$ has a colourful partition of size at most $k$. This problem is closely related to the COLOURFUL COMPONENTS problem, which is to decide whether a graph can be modified into a graph whose connected components form a colourful partition by deleting at most $p$ edges. Nevertheless we show that COLOURFUL PARTITION and COLOURFUL COMPONENTS may have different complexities for restricted instances. We tighten known NP-hardness results for both problems and in addition we prove new hardness and tractability results for COLOURFUL PARTITION. Using these results we complete our paper with a thorough parameterized study of COLOURFUL PARTITION.

In metabolomics, small molecules are structurally elucidated using tandem mass spectrometry (MS/MS); this resulted in the computational Maximum Colorful Subtree problem, which is NP-hard. Unfortunately, data from a single metabolite requires us to solve hundreds or thousands of instances of this problem; and in a single Liquid Chromatography MS/MS run, hundreds or thousands of metabolites are measured. Here, we comprehensively evaluate the performance of several heuristic algorithms for the problem against an exact algorithm. We put particular emphasis on whether a heuristic is able to rank candidates such that the correct solution is ranked highly. We propose this "intermediate" evaluation because evaluating the approximating quality of heuristics is misleading: Even a slightly suboptimal solution can be structurally very different from the true solution. On the other hand, we cannot structurally evaluate against the ground truth, as this is unknown. We find that one particular heuristic consistently ranks the correct solution in a top position, allowing us to speed up computations about 100-fold. We also find that scores of the best heuristic solutions are very close to the optimal score; in contrast, the structure of the solutions can deviate significantly from the optimal structures.

In Genomic Scaffold Filling, one aims at polishing in silico a draft genome, called scaffold. The scaffold is given in the form of an ordered set of gene sequences, called contigs. This is done by confronting the scaffold to an already complete reference genome from a close species. More precisely, given a scaffold S, a reference genome G and a score function f() between two genomes, the aim is to complete S by adding the missing genes from G so that the obtained complete genome S* optimizes f(S*, G). In this paper, we extend a model of Jiang et al. [CPM 2016] (i) by allowing the insertions of strings instead of single characters (i.e., some groups of genes may be forced to be inserted together) and (ii) by considering two alternative score functions: the first generalizes the notion of common adjacencies by maximizing the number of common k-mers between S* and G (k-Mer Scaffold Filling), the second aims at minimizing the number of breakpoints between S* and G (Min-Breakpoint Scaffold Filling). We study these problems from the parameterized complexity point of view, providing fixed-parameter (FPT) algorithms for both problems. In particular, we show that k-Mer Scaffold Filling is FPT wrt. parameter l, the number of additional k-mers realized by the completion of S—this answers an open question of Jiang et al. [CPM 2016]. We also show that Min-Breakpoint Scaffold Filling is FPT wrt. a parameter combining the number of missing genes, the number of gene repetitions and the target distance.

BACKGROUND: Given two genomes that have diverged by a series of rearrangements, we infer minimum Double Cut-and-Join (DCJ) scenarios to explain their organization differences, coupled with indel scenarios to explain their intergene size distribution, where DCJs themselves also alter the sizes of broken intergenes. RESULTS: We give a polynomial-time algorithm that, given two genomes with arbitrary intergene size distributions, outputs a DCJ scenario which optimizes on the number of DCJs, and given this optimal number of DCJs, optimizes on the total sum of the sizes of the indels. CONCLUSIONS: We show that there is a valuable information in the intergene sizes concerning the rearrangement scenario itself. On simulated data we show that statistical properties of the inferred scenarios are closer to the true ones than DCJ only scenarios, i.e. scenarios which do not handle intergene sizes.

Genomes present various types of repeated structures having important roles in the mechanism of evolution. In particular, tandem repeats are analysed for their impact on genetic backgrounds of inherited diseases. However, the main objective of today's de novo assemblers is to output long, high-quality, assembled sequences; to this end, they use heuristic-based assembling procedures, which can leave many repeated regions unassembled - and in particular exact tandem repeats - due to the genomes complexity. In this paper, we propose an effective method, called DExTaR, that improves the detection of exact tandem repeats (ETRs) in any de novo de Bruijn assembly. DExTaR is based on a de Bruijn graph constructed by an assembler and retrieves ETRs left unassembled. When used with the well-known assembler ABySS, we show that DExTaR is able to obtain high quality results in terms of number and length of the detected ETRs.

In comparative genomics, a transposition is an operation that exchanges two consecutive sequences of genes in a genome. The transposition distance between two genomes, that is, the minimum number of transpositions needed to transform a genome into another, is, according to numerous studies, a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations is called the Sorting by Transpositions problem, and has been introduced by Bafna and Pevzner in [Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995, pp. 614--623]. It has naturally been the focus of a number of studies (see, for instance, [G. Fertin, A. Labarre, I. Rusu, É. Tannier, and S. Vialette, Combinatorics of Genome Rearrangements, The MIT Press, Cambridge, MA, 2009]), but the computational complexity of this problem has remained undetermined for 15 years. In this paper, we answer this long-standing open question by proving that the Sorting by Transpositions problem is \sf NP-hard. As a corollary of our result, we also prove that the following problem, first described in [D. A. Christie, Genome Rearrangement Problems, Ph.D. thesis, University of Glasgow, Glasgow, Scotland, 1998], is \sf NP-hard: given a permutation $\pi$, is it possible to sort $\pi$ using exactly $d_b(\pi)/3$ transpositions, where $d_b(\pi)$ is the number of breakpoints of $\pi$?

In this paper, we are interested in the computational complexity of computing (dis)similarity measures between two genomes when they contain duplicated genes or genomic markers, a problem that happens frequently when comparing whole nuclear genomes. Recently, several methods ( [1], [2]) have been proposed that are based on two steps to compute a given (dis)similarity measure M between two genomes G_1 and G_2: first, one establishes a oneto- one correspondence between genes of G_1 and genes of G_2 ; second, once this correspondence is established, it defines explicitly a permutation and it is then possible to quantify their similarity using classical measures defined for permutations, like the number of breakpoints. Hence these methods rely on two elements: a way to establish a one-to-one correspondence between genes of a pair of genomes, and a (dis)similarity measure for permutations. The problem is then, given a (dis)similarity measure for permutations, to compute a correspondence that defines an optimal permutation for this measure. We are interested here in two models to compute a one-to-one correspondence: the exemplar model, where all but one copy are deleted in both genomes for each gene family, and the matching model, that computes a maximal correspondence for each gene family. We show that for these two models, and for three (dis)similarity measures on permutations, namely the number of common intervals, the maximum adjacency disruption (MAD) number and the summed adjacency disruption (SAD) number, the problem of computing an optimal correspondence is NP-complete, and even APXhard for the MAD number and SAD number.

In this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence of a set of sequences (ELCS problem), a generalization of the Longest Common Subsequence problem, where the input sequences are over the union of two disjoint sets of symbols, a set of mandatory symbols and a set of optional symbols. We show that different versions of the problem are APX-hard even for instances with two sequences. Moreover, we show that the related problem of determining the existence of a feasible solution of the Exemplar Longest Common Subsequence of two sequences is NP-hard. On the positive side, we first present an efficient algorithm for the ELCS problem over instances of two sequences where each mandatory symbol can appear in total at most three times in the sequences. Furthermore, we present two fixed-parameter algorithms for the ELCS problem over instances of two sequences where the parameter is the number of mandatory symbols.

Gossiping refers to the following task: In a group of individuals connected by a communication network, every node has a piece of information and needs to transmit it to all the nodes in the network. The networks are modeled by graphs, where the vertices represent the nodes, and the edges, the communication links. In this paper, we concentrate on minimum gossip graphs of even order, that is, graphs able to achieve gossiping in minimum time and with a minimum number of links. More precisely, we derive upper bounds for their number of edges from a compounding method, the k-way split method, previously introduced for broadcasting by Farley [Networks 9 (1979), 313–332]. We show that this method can be applied to gossiping in some cases and that this generalizes some compounding methods for gossip graphs given in [5]. We also show that, when applicable, this method gives the best-known upper bounds on the size of minimum gossip graphs in most cases, either improving or matching them. Notably, we present for the first time two families of regular gossip graphs of order n and of degree ⌈log2(n)⌉ − 3 and ⌈log2(n)⌉ − 4, respectively. We also give some lower bounds on the number of edges of gossip graphs which improve the ones given by Fertin [5]. Moreover, we show that the above compounding method also applies for minimum linear gossip graphs (or MLGGs) of even order, which corresponds to a variant of gossiping where the time of information transmission between two nodes depends on the amount of information exchanged. We also prove that this gives the best-known upper bounds for Gβ,τ(n)—the size of an MLGG of order n—in most cases. In particular, we derive from this method the exact value of Gβ,τ(72), which was previously unknown. © 2000 John Wiley & Sons, Inc.