Abstract
Motivation
There are very few methods for de novo genome assembly based on the overlap graph approach. It is considered as giving more exact results than the so-called de Bruijn graph ...approach but in much greater time and of much higher memory usage. It is not uncommon that assembly methods involving the overlap graph model are not able to successfully compute greater datasets, mainly due to memory limitation of a computer. This was the reason for developing in last decades mainly de Bruijn-based assembly methods, fast and fairly accurate. However, the latter methods can fail for longer or more repetitive genomes, as they decompose reads to shorter fragments and lose a part of information. An efficient assembler for processing big datasets and using the overlap graph model is still looked out.
Results
We propose a new genome-scale de novo assembler based on the overlap graph approach, designed for short-read sequencing data. The method, ALGA, incorporates several new ideas resulting in more exact contigs produced in short time. Among these ideas, we have creation of a sparse but quite informative graph, reduction of the graph including a procedure referring to the problem of minimum spanning tree of a local subgraph, and graph traversal connected with simultaneous analysis of contigs stored so far. What is rare in genome assembly, the algorithm is almost parameter-free, with only one optional parameter to be set by a user. ALGA was compared with nine state-of-the-art assemblers in tests on genome-scale sequencing data obtained from real experiments on six organisms, differing in size, coverage, GC content and repetition rate. ALGA produced best results in the sense of overall quality of genome reconstruction, understood as a good balance between genome coverage, accuracy and length of resulting sequences. The algorithm is one of tools involved in processing data in currently realized national project Genomic Map of Poland.
Availability and implementation
ALGA is available at http://alga.put.poznan.pl.
Supplementary information
Supplementary data are available at Bioinformatics online.
Chessboard and chess piece recognition is a computer vision problem that has not yet been efficiently solved. Digitization of a chess game state from a picture of a chessboard is a task typically ...performed by humans or with the aid of specialized chessboards and pieces. However, those solutions are neither easy nor convenient. To solve this problem, we propose a novel algorithm for digitizing chessboard configurations.
We designed a method of chessboard recognition and pieces detection that is resistant to lighting conditions and the angle at which images are captured, and works correctly with numerous chessboard styles. Detecting the board and recognizing chess pieces are crucial steps of board state digitization.
The algorithm achieves 95% accuracy (compared to 60% for the best alternative) for positioning the chessboard in an image, and almost 95% for chess pieces recognition. Furthermore, the sub-process of detecting straight lines and finding lattice points performs extraordinarily well, achieving over 99.5% accuracy (compared to the 74% for the best alternative).
Next generation sequencers produce billions of short DNA sequences in a massively parallel manner, which causes a great computational challenge in accurately reconstructing a genome sequence de novo ...using these short sequences. Here, we propose the GRASShopPER assembler, which follows an approach of overlap-layout-consensus. It uses an efficient GPU implementation for the sequence alignment during the graph construction stage and a greedy hyper-heuristic algorithm at the fork detection stage. A two-part fork detection method allows us to identify repeated fragments of a genome and to reconstruct them without misassemblies. The assemblies of data sets of bacteria Candidatus Microthrix, nematode Caenorhabditis elegans, and human chromosome 14 were evaluated with the golden standard tool QUAST. In comparison with other assemblers, GRASShopPER provided contigs that covered the largest part of the genomes and, at the same time, kept good values of other metrics, e.g., NG50 and misassembly rate.
Full text
Available for:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, SIK, UILJ, UKNU, UL, UM, UPUK
Online judges are systems designed for the reliable evaluation of algorithm source code submitted by users, which is next compiled and tested in a homogeneous environment. Online judges are becoming ...popular in various applications. Thus, we would like to review the state of the art for these systems. We classify them according to their principal objectives into systems supporting organization of competitive programming contests, enhancing education and recruitment processes, facilitating the solving of data mining challenges, online compilers and development platforms integrated as components of other custom systems. Moreover, we introduce a formal definition of an online judge system and summarize the common evaluation methodology supported by such systems. Finally, we briefly discuss an Optil.io platform as an example of an online judge system, which has been proposed for the solving of complex optimization problems. We also analyze the competition results conducted using this platform. The competition proved that online judge systems, strengthened by crowdsourcing concepts, can be successfully applied to accurately and efficiently solve complex industrial- and science-driven challenges.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, SAZU, UL, UM, UPUK
Chessboard and chess piece recognition is a computer vision problem that has not yet been efficiently solved. However, its solution is crucial for many experienced players who wish to compete against ...AI bots, but also prefer to make decisions based on the analysis of a physical chessboard. It is also important for organizers of chess tournaments who wish to digitize play for online broadcasting or ordinary players who wish to share their gameplay with friends. Typically, such digitization tasks are performed by humans or with the aid of specialized chessboards and pieces. However, neither solution is easy or convenient. To solve this problem, we propose a novel algorithm for digitizing chessboard configurations. We designed a method that is resistant to lighting conditions and the angle at which images are captured, and works correctly with numerous chessboard styles. The proposed algorithm processes pictures iteratively. During each iteration, it executes three major sub-processes: detecting straight lines, finding lattice points, and positioning the chessboard. Finally, we identify all chess pieces and generate a description of the board utilizing standard notation. For each of these steps, we designed our own algorithm that surpasses existing solutions. We support our algorithms by utilizing machine learning techniques whenever possible. The described method performs extraordinarily well and achieves an accuracy over \(99.5\%\) for detecting chessboard lattice points (compared to the \(74\%\) for the best alternative), \(95\%\) (compared to \(60\%\) for the best alternative) for positioning the chessboard in an image, and almost \(95\%\) for chess piece recognition.
This paper concludes the Brilliant Challenges contest. Participants had to design interesting optimization problems and publish them using the Optil.io platform. It was the first widely-advertised ...contest in the area of operational research where the objective was to submit the problem definition instead of the algorithmic solutions. Thus, it is a crucial contribution to Open Science and the application of crowdsourcing methodology to solve discrete optimization problems. The paper briefly describes submitted problems, presents the winners, and discusses the contest's achievements and shortcomings. Finally, we define guidelines supporting the organization of contests of similar type in the future.
Reliable and trustworthy evaluation of algorithms is a challenging process. Firstly, each algorithm has its strengths and weaknesses, and the selection of test instances can significantly influence ...the assessment process. Secondly, the measured performance of the algorithm highly depends on the test environment architecture, i.e., CPU model, available memory, cache configuration, operating system's kernel, and even compilation flags. Finally, it is often difficult to compare algorithm with software prepared by other researchers. Evaluation as a Service (EaaS) is a cloud computing architecture that tries to make assessment process more reliable by providing online tools and test instances dedicated to the evaluation of algorithms. One of such platforms is Optil.io which gives the possibility to define problems, store evaluation data and evaluate solutions submitted by researchers in almost real time. In this paper, we briefly present this platform together with four challenges that were organized with its support.
Online judges are systems designed for the reliable evaluation of algorithm source code submitted by users, which is next compiled and tested in a homogeneous environment. Online judges are becoming ...popular in various applications. Thus, we would like to review the state of the art for these systems. We classify them according to their principal objectives into systems supporting organization of competitive programming contests, enhancing education and recruitment processes, facilitating the solving of data mining challenges, online compilers and development platforms integrated as components of other custom systems. Moreover, we introduce a formal definition of an online judge system and summarize the common evaluation methodology supported by such systems. Finally, we briefly discuss an Optil.io platform as an example of an online judge system, which has been proposed for the solving of complex optimization problems. We also analyze the competition results conducted using this platform. The competition proved that online judge systems, strengthened by crowdsourcing concepts, can be successfully applied to accurately and efficiently solve complex industrial- and science-driven challenges.
Abstract
We propose an optimal and efficient numerical test for witnessing genuine multipartite nonlocality based on a geometric approach. In particular, we consider two non-equivalent models of ...local hidden variables, namely the Svetlichny and the no-signaling bilocal models. While our knowledge concerning these models is well established for Bell-type scenarios involving two measurement settings per party, the general case based on an arbitrary number of settings is a considerably more challenging task and very little work has been done in this field. In this paper, we applied such general tests to detect and characterize genuine
n
-way nonlocal correlations for various states of three qubits and qutrits. Apart from the fundamental problem of characterizing genuine multipartite nonlocal correlations, the extension of the number of measurements beyond two is also of practical importance. As a measure of nonlocality, we use the probability of violation of local realism under randomly sampled observables, and the strength of nonlocality, described by the resistance to white noise admixture. In particular, we analyze to what extent the Bell-type scenario involving two measurement settings can be used to certify genuine
n
-way nonlocal correlations generated for more general models. In addition, we propose a simple procedure to detect such nonlocal correlations for randomly chosen settings with an efficiency of up to 100%. Due to its near-perfect efficiency, our method may open new possibilities in device-independent quantum cryptography applications where strong nonlocality between all partners is required.
PDF
