RESUMEN

PURPOSE: This study describes a real-time spot weight adaptation method in spot-scanning proton therapy for moving target or moving patient, so that the resultant dose distribution closely matches the planned dose distribution. MATERIALS AND METHODS: The method proposed in this study adapts the weight (MU) of the delivering pencil beam to that of the target spot; it will actually hit during patient/target motion. The target spot that a certain delivering pencil beam may hit relies on patient monitoring and/or motion modeling using four-dimensional (4D) CT. After the adapted delivery, the required total weight [Monitor Unit (MU)] for this target spot is then subtracted from the planned value. With continuous patient motion and continuous spot scanning, the planned doses to all target spots will eventually be all fulfilled. In a proof-of-principle test, a lung case was presented with realistic temporal and motion parameters; the resultant dose distribution using spot weight adaptation was compared to that without using this method. The impact of the real-time patient/target position tracking or prediction was also investigated. RESULTS: For moderate motion (i.e., mean amplitude 0.5 cm), D95% to the planning target volume (PTV) was only 81.5% of the prescription (RX) dose; with spot weight adaptation PTV D95% achieves 97.7% RX. For large motion amplitude (i.e., 1.5 cm), without spot weight adaptation PTV D95% is only 42.9% of RX; with spot weight adaptation, PTV D95% achieves 97.7% RX. Larger errors in patient/target position tracking or prediction led to worse final target coverage; an error of 3 mm or smaller in patient/target position tracking is preferred. CONCLUSION: The proposed spot weight adaptation method was able to deliver the planned dose distribution and maintain target coverage when patient motion was involved. The successful implementation of this method would rely on accurate monitoring or prediction of patient/target motion.

RESUMEN

Recent techniques increase rapidly the amount of our knowledge on interactions between proteins. The interpretation of these new information depends on our ability to retrieve known substructures in the data, the Protein-Protein Interactions (PPIs) networks. In an algorithmic point of view, it is an hard task since it often leads to NP-hard problems. To overcome this difficulty, many authors have provided tools for querying patterns with a restricted topology, i.e., paths or trees in PPI networks. Such restriction leads to the development of fixed parameter tractable (FPT) algorithms, which can be practicable for restricted sizes of queries. Unfortunately, Graph Homomorphism is a W[1]-hard problem, and hence, no FPT algorithm can be found when patterns are in the shape of general graphs. However, Dost et al. gave an algorithm (which is not implemented) to query graphs with a bounded treewidth in PPI networks (the treewidth of the query being involved in the time complexity). In this paper, we propose another algorithm for querying pattern in the shape of graphs, also based on dynamic programming and the color-coding technique. To transform graphs queries into trees without loss of informations, we use feedback vertex set coupled to a node duplication mechanism. Hence, our algorithm is FPT for querying graphs with a bounded size of their feedback vertex set. It gives an alternative to the treewidth parameter, which can be better or worst for a given query. We provide a python implementation which allows us to validate our implementation on real data. Especially, we retrieve some human queries in the shape of graphs into the fly PPI network.

Asunto(s)

Asunto(s)

RESUMEN

Comparing genomes of different species is a fundamental problem in comparative genomics. Recent research has resulted in the introduction of different measures between pairs of genomes: for example, reversal distance, number of breakpoints, and number of common or conserved intervals. However, classical methods used for computing such measures are seriously compromised when genomes have several copies of the same gene scattered across them. Most approaches to overcome this difficulty are based either on the exemplar model, which keeps exactly one copy in each genome of each duplicated gene, or on the maximum matching model, which keeps as many copies as possible of each duplicated gene. The goal is to find an exemplar matching, respectively a maximum matching, that optimizes the studied measure. Unfortunately, it turns out that, in presence of duplications, this problem for each above-mentioned measure is NP-hard. In this paper, we propose to compute the minimum number of breakpoints and the maximum number of adjacencies between two genomes in presence of duplications using two different approaches. The first one is an exact, generic 0-1 linear programming approach, while the second is a collection of three heuristics. Each of these approaches is applied on each problem and for each of the following models: exemplar, maximum matching and intermediate model, that we introduce here. All these programs are run on a well-known public benchmark dataset of gamma-Proteobacteria, and their performances are discussed.

Asunto(s)

RESUMEN

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.

Asunto(s)

RESUMEN

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.

Asunto(s)

RESUMEN

Computing genomic distances between whole genomes is a fundamental problem in comparative genomics. Recent researches have resulted in different genomic distance definitions, for example, number of breakpoints, number of common intervals, number of conserved intervals, and Maximum Adjacency Disruption number. Unfortunately, it turns out that, in presence of duplications, most problems are NP-hard, and hence several heuristics have been recently proposed. However, while it is relatively easy to compare heuristics between them, until now very little is known about the absolute accuracy of these heuristics. Therefore, there is a great need for algorithmic approaches that compute exact solutions for these genomic distances. In this paper, we present a novel generic pseudo-boolean approach for computing the exact genomic distance between two whole genomes in presence of duplications, and put strong emphasis on common intervals under the maximum matching model. Of particular importance, we show three heuristics which provide very good results on a well-known public dataset of gamma-Proteobacteria.

Asunto(s)

RESUMEN

MOTIVATION: Molecular evolution, which is classically assessed by comparison of individual proteins or genes between species, can now be studied by comparing co-expressed functional groups of genes. This approach, which better reflects the functional constraints on the evolution of organisms, can exploit the large amount of data generated by genome-wide expression analyses. However, it requires new methodologies to represent the data in a more accessible way for cross-species comparisons. RESULTS: In this work, we present an approach based on Multi-dimensional Scaling techniques, to compare the conformation of two gene expression networks, represented in a multi-dimensional space. The expression networks are optimally superimposed, taking into account two criteria: (1) inter-organism orthologous gene pairs have to be nearby points in the final multi-dimensional space and (2) the distortion of the gene expression networks, the organization of which reflects the similarities between the gene expression measurements, has to be circumscribed. Using this approach, we compared the transcriptional programs that drive sporulation in budding and fission yeasts, extracting some common properties and differences between the two species.

Asunto(s)

RESUMEN

BACKGROUND: Information obtained by DNA microarray technology gives a rough snapshot of the transcriptome state, i.e., the expression level of all the genes expressed in a cell population at any given time. One of the challenging questions raised by the tremendous amount of microarray data is to identify groups of co-regulated genes and to understand their role in cell functions. RESULTS: MiCoViTo (Microarray Comparison Visualization Tool) is a set of biologists' tools for exploring, comparing and visualizing changes in the yeast transcriptome by a gene-centric approach. A relational database includes data linked to genome expression and graphical output makes it easy to visualize clusters of co-expressed genes in the context of available biological information. To this aim, upload of personal data is possible and microarray data from fifty publications dedicated to S. cerevisiae are provided on-line. A web interface guides the biologist during the usage of this tool and is freely accessible at http://www.transcriptome.ens.fr/micovito/. CONCLUSIONS: MiCoViTo offers an easy-to-read picture of local transcriptional changes connected to current biological knowledge. This should help biologists to mine yeast microarray data and better understand the underlying biology. We plan to add functional annotations from other organisms. That would allow inter-species comparison of transcriptomes via orthology tables.

Asunto(s)

RESUMEN

The yeast Microarray Global Viewer (yMGV @ http://transcriptome.ens.fr/ymgv) was created 3 years ago as a database that houses a collection of Saccharomyces cerevisiae and Schizosaccharo myces pombe microarray data sets published in 82 different articles. yMGV couples data mining tools with a user-friendly web interface so that, with a few mouse clicks, one can identify the conditions that affect the expression of a gene or list of genes regulated in a set of experiments. One of the major new features we present here is a set of tools that allows for inter-organism comparisons. This should enable the fission yeast community to take advantage of the large amount of available information on budding yeast transcriptome. New tools and ongoing developments are also presented here.

Asunto(s)

RESUMEN

BACKGROUND: Subcellular messenger RNA localization is important in most eukaryotic cells, even in unicellular organisms like yeast for which this process has been underestimated. Microarrays are rarely used to study subcellular mRNA localization at whole-genome level, but can be adapted to that purpose. This work focuses on studying the repartition of yeast nuclear transcripts encoding mitochondrial proteins between free cytosolic polysomes and polysomes bound to the mitochondrial outer membrane. RESULTS: Combining biochemical fractionations with oligonucleotide array analyses permits clustering of genes on the basis of the subcellular sites of their mRNA translation. A large fraction of yeast nuclear transcripts known to encode mitochondrial proteins is found in mitochondrial outer-membrane-bound fractions. These results confirm and extend a previous analysis conducted with partial genomic microarrays. Interesting statistical relations among mRNA localization, gene origin and mRNA lengths were found: longer and older mRNAs are more prone to be localized to the vicinity of mitochondria. These observations are included in a refined model of mitochondrial protein import. CONCLUSIONS: Mitochondrial biogenesis requires concerted expression of the many genes whose products make up the organelle. In the absence of any clear transcriptional program, coordinated mRNA localization could be an important element of the time-course of organelle construction. We have built a 'MitoChip' localization database from our results which allows us to identify interesting genes whose mRNA localization might be essential for mitochondrial biogenesis in most eukaryotic cells. Moreover, many components of the experimental and data-analysis strategy implemented here are of general relevance in global transcription studies.

Asunto(s)

RESUMEN

We recently demonstrated that polysome-associated mRNAs that co-isolate with mitochondria encode a subset of mitochondrial proteins, and that the 3' UTRs of these transcripts are essential for their localization to the vicinity of the organelle. To address the question of the involvement of the mRNA targeting process in mitochondrial biogenesis, we studied the role of ATP2 3' UTR. An altered ATP2 allele in which the 3' UTR was replaced by the ADH1 3' UTR exhibits properties supporting the importance of mRNA localization to the vicinity of mitochondria: (i) the mutated strain presents a respiratory dysfunction; (ii) mitochondrial import of the protein translated from the altered gene is strongly reduced, even though the precursor is addressed to the organelle surface; (iii) systematic deletions of ATP2 3' UTR revealed a 100 nucleotide element presenting RNA targeting properties. Additionally, when the ATM1 3' UTR was replaced by the ADH1 3' UTR, we obtained cells in which ATM1 mRNA is also delocalized, and presenting a respiratory dysfunction. This demonstrates that mRNA localization to the vicinity of mitochondria plays a critical role in organelle biogenesis.

Asunto(s)