We address the problem of building and evaluating a computational system whose primary objective is creativity. We illustrate seven characteristics for computational creativity in the context of a system that autonomously composes Western lyrical music. We conduct an external evaluation of the system in which respondents rated the system with regard to each characteristic as well as with regard to overall creativity. Average scores for overall creativity exceeded the ratings for any single characteristic, suggesting that creativity may be an emergent property and that unique research opportunities exist for building CC systems whose design attempts to comprehend all known characteristics of creativity.

Whereas interactive dynamic visualization tools have been successfully developed and used for teaching some topics in computational theory (CT), there remains a noticeable lack of such tools for teaching NP-completeness which continues to be widely taught using paper-and-pencil methods. Despite its important theoretical and practical value, NP-completeness-and mapping reductions in NP-completeness in particular-tends to be a challenging concept for CT students to understand. We present an open-source web app called Redux that provides a dynamic interactive user interface atop a practical knowledge base of NP-complete problems, reductions, and solution algorithms. A key feature of the interface is the visualization of arbitrary problem instances, mapping reductions, solutions, and gadgets-including those reachable via transitivity. The web app is designed to make the knowledge base extensible, allowing students to contribute and compare their reductions and solutions to those already available. Two surveys were administered, with respondents overwhelmingly indicating that Redux helped them to better understand mapping reductions; that they would prefer using Redux to solve similar problems manually; and that Redux makes learning NP-complete reductions more enjoyable. Redux is accessible online via https://redux.portneuf.cose.isu.edu/.

Keystroke data in programming reveals intricate patterns that reflect the behavior of programmers. These patterns hold promise for predicting grades and other applications, providing insights into the skills of both proficient and less proficient programmers. Analyzing these patterns can yield tailored feedback for students who need support, enabling effective interventions. Our study utilizes a keystroke dataset from the CS1 (Introduction to Computer Science) course at Utah State University. We developed novel features by combining elements like key presses, timestamps, source locations, and programming terminology, drawing on prior research, our insights, and an analysis of programming behavior. An ensemble-based feature selection method identifies key features, which are then used in hyperparameter optimization and grade prediction with six classification and three regression algorithms. We categorized grades into three levels: Low, Average, and High. Despite challenges such as class imbalance, plagiarism, limited data per assignment, and the ceiling effect, we attained a notable weighted F1 score of 78%. We also introduce an ensemble classification strategy, merging Isolation Forest outlier detection with a refined Random Forest classifier, achieving 80% accuracy on our test set. Additionally, we provide a detailed interpretation of our features, supported by results and a case study of our dataset. This research aims to enhance computer science education at the undergraduate level, focusing on improving its overall quality. Code and data are available https://github.com/DSAatUSU/Student-Coding-Behavior.git.

We present a formalized rhyme function for machine approximation of human rhyme. Words are represented as sequences of phonemic features that facilitate the use of alignment mechanisms to compute different types of phonemic similarities between words. The rhyme function computes a weighted hierarchical combination of these similarities, with the weights determined using an evolutionary approach. We present empirical and qualitative analyses that demonstrate the rhyme function's ability to successfully detect rhyme, and we briefly discuss the model's linguistic basis and its resulting generality.

Codon bias, the usage patterns of synonymous codons for encoding a protein sequence as nucleotides, is a biological phenomenon that is not fully understood. Several methods exist to represent the codon bias of an organism: codon adaptation index (CAI) [1], individual codon usage (ICU), hidden stop codons (HSC) [2] and codon context (CC) [3]. These methods are often employed in the optimization of heterologous gene expression to increase the accuracy and rate of translation. They, however, have many shortcomings as they dont take into account the local and global context of a gene. We present a method for modeling global and local codon bias through deep language models that is more robust than current methods by providing more contextual information and long-range dependencies.

Comparing genomes to identify polymorphisms is a difficult task, especially beyond single nucleotide poly-morphisms. Polymorphism detection is important in disease association studies as well as in phylogenetic tree reconstruc-tion. We present a method for identifying polymorphisms in genomes by using a modified version de Bruijn graphs, data structures widely used in genome assembly from Next-Generation Sequencing. Using our method, we are able to identify polymorphisms that exist within a genome as well as well as see graph structures that form in the de Bruijn graph for particular types of polymorphisms (translocations, etc.).

We present kleuren, a novel assembly-free method to reconstruct phylogenetic trees using the Colored de Bruijn Graph. kleuren works by constructing the Colored de Bruijn Graph and then traversing it, finding bubble structures in the graph that provide phylogenetic signal. The bubbles are then aligned and concatenated to form a supermatrix, from which a phylogenetic tree is inferred. We introduce the algorithms that kleuren uses to accomplish this task, and show its performance on reconstructing the phylogenetic tree of 12 Drosophila species. kleuren reconstructed the established phylogenetic tree accurately, and is a viable tool for phylogenetic tree reconstruction using whole genome sequences. Software package available at: https://github.com/Colelyman/kleuren.

MOTIVATION: The contig orientation problem, which we formally define as the MAX-DIR problem, has at times been addressed cursorily and at times using various heuristics. In setting forth a linear-time reduction from the MAX-CUT problem to the MAX-DIR problem, we prove the latter is NP-complete. We compare the relative performance of a novel greedy approach with several other heuristic solutions. RESULTS: Our results suggest that our greedy heuristic algorithm not only works well but also outperforms the other algorithms due to the nature of scaffold graphs. Our results also demonstrate a novel method for identifying inverted repeats and inversion variants, both of which contradict the basic single-orientation assumption. Such inversions have previously been noted as being difficult to detect and are directly involved in the genetic mechanisms of several diseases. AVAILABILITY AND IMPLEMENTATION: http://bioresearch.byu.edu/scaffoldscaffolder. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Genome-wide association studies (GWAS) have effectively identified genetic factors for many diseases. Many diseases, including Alzheimer's disease (AD), have epistatic causes, requiring more sophisticated analyses to identify groups of variants which together affect phenotype. RESULTS: Based on the GWAS statistical model, we developed a multi-SNP GWAS analysis to identify pairs of variants whose common occurrence signaled the Alzheimer's disease phenotype. CONCLUSIONS: Despite not having sufficient data to demonstrate significance, our preliminary experimentation identified a high correlation between GRIA3 and HLA-DRB5 (an AD gene). GRIA3 has not been previously reported in association with AD, but is known to play a role in learning and memory.

BACKGROUND: Genome assemblers to date have predominantly targeted haploid reference reconstruction from homozygous data. When applied to diploid genome assembly, these assemblers perform poorly, owing to the violation of assumptions during both the contigging and scaffolding phases. Effective tools to overcome these problems are in growing demand. Increasing parameter stringency during contigging is an effective solution to obtaining haplotype-specific contigs; however, effective algorithms for scaffolding such contigs are lacking. METHODS: We present a stand-alone scaffolding algorithm, ScaffoldScaffolder, designed specifically for scaffolding diploid genomes. The algorithm identifies homologous sequences as found in "bubble" structures in scaffold graphs. Machine learning classification is used to then classify sequences in partial bubbles as homologous or non-homologous sequences prior to reconstructing haplotype-specific scaffolds. We define four new metrics for assessing diploid scaffolding accuracy: contig sequencing depth, contig homogeneity, phase group homogeneity, and heterogeneity between phase groups. RESULTS: We demonstrate the viability of using bubbles to identify heterozygous homologous contigs, which we term homolotigs. We show that machine learning classification trained on these homolotig pairs can be used effectively for identifying homologous sequences elsewhere in the data with high precision (assuming error-free reads). CONCLUSION: More work is required to comparatively analyze this approach on real data with various parameters and classifiers against other diploid genome assembly methods. However, the initial results of ScaffoldScaffolder supply validity to the idea of employing machine learning in the difficult task of diploid genome assembly. Software is available at http://bioresearch.byu.edu/scaffoldscaffolder.

BACKGROUND: Error correction is an important step in increasing the quality of next-generation sequencing data for downstream analysis and use. Polymorphic datasets are a challenge for many bioinformatic software packages that are designed for or assume homozygosity of an input dataset. This assumption ignores the true genomic composition of many organisms that are diploid or polyploid. In this survey, two different error correction packages, Quake and ECHO, are examined to see how they perform on next-generation sequence data from heterozygous genomes. RESULTS: Quake and ECHO perform well and were able to correct many errors found within the data. However, errors that occur at heterozygous positions had unique trends. Errors at these positions were sometimes corrected incorrectly, introducing errors into the dataset with the possibility of creating a chimeric read. Quake was much less likely to create chimeric reads. Quake's read trimming removed a large portion of the original data and often left reads with few heterozygous markers. ECHO resulted in more chimeric reads and introduced more errors than Quake but preserved heterozygous markers. CONCLUSIONS: These findings suggest that Quake and ECHO both have strengths and weaknesses when applied to heterozygous data. With the increased interest in haplotype specific analysis, new tools that are designed to be haplotype-aware are necessary that do not have the weaknesses of Quake and ECHO.