中央研究院 資訊科學研究所

圖書室

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

2019 Technical Report

:::

論文代碼
標題 / 作者 / 摘要
檢視

論文代碼

TR-IIS-19-001

標題 / 作者 / 摘要

A Prehistoric Calculator
Kelly McKennon

It is shown how a certain prehistoric symbol can be used as a calculator to compute sums, differences, products, quotients and square roots. As an example, this symbol is used to compute the dimensions of a typical building block of the great pyramid of Giza.

檢視

Fulltext

論文代碼

TR-IIS-19-002

標題 / 作者 / 摘要

Equational reasoning for non-determinism monad: the case of Spark aggregation
Shin-Cheng Mu

As part of the author's studies on equational reasoning for monadic programs, this report focus on non-determinism monad. We discuss what properties this monad should satisfy, what additional operators and notations can be introduced to facilitate equational reasoning about non-determinism, and put them to the test by proving a number of properties in our example problem inspired by the author's previous work on proving properties of Spark aggregation.

檢視

Fulltext

論文代碼

TR-IIS-19-003

標題 / 作者 / 摘要

Calculating a backtracking algorithm: an exercise in monadic program derivation
Shin-Cheng Mu

Equational reasoning is among the most important tools that functional programming provides us. Curiously, relatively less attention has been paid to reasoning about monadic programs. In this report we derive a backtracking algorithm for problem specifications that use a monadic unfold to generate possible solutions, which are filtered using a scanl-like predicate. We develop theorems that convert a variation of scanl to a foldr that uses the state monad, as well as theorems constructing hylomorphism.

The algorithm is used to solve the n-queens puzzle, our running example. The aim is to develop theorems and patterns useful for the derivation of monadic programs, focusing on the intricate interaction between state and non-determinism.

檢視

Fulltext

論文代碼

IM-IIS-19-001

標題 / 作者 / 摘要

MinProtMaxVP: Generating a minimized number of protein variant sequences containing all possible variant peptides by solving a set covering problem
Wai-Kok Choong, Jen-Hung Wang, and Ting-Yi Sung

Identifying single-amino-acid variants (SAVs) from mass spectrometry-based experiments is critical for validating single-nucleotide variants (SNVs) at the protein level to facilitate biomedical research. Currently, two approaches are usually applied to convert SNV annotations into SAV-harboring protein sequences. One approach generates one sequence containing exactly one SAV, and the other all SAVs. However, they may neglect the possibility of SAV combinations, e.g., haplotypes, existing in bio-samples. Therefore, it is necessary to consider all SAV combinations of a protein when generating SAV-harboring protein sequences. However, such an exhaustive approach yields a large number of sequences and many redundant peptides among these sequences. In this paper, we propose a novel approach, called MinProtMaxVP, that selects a minimized number of SAV-harboring protein sequences generated from the exhaustive approach, while still accommodating all possible variant peptides, by solving a classic set covering problem. Our study on known haplotype variations of TAS2R38 justified MinProtMaxVP’s necessity of considering all combinations of SAVs. The study on OR2T27 with five SAVs showed the outperformance of MinProtMaxVP. Furthermore, assuming simulated somatic and germline variants of OR2T27 in tumor and normal tissues demonstrated that when adopting the appropriate somatic and germline SAV integration strategy, MinProtMaxVP is adaptable to labeling and label-free mass spectrometry-based experiments.

檢視

not for public 原文請洽圖書室