# Questions tagged [algorithms]

The tag has no usage guidance, but it has a tag wiki.

51 questions
Filter by
Sorted by
Tagged with
59 views

### Multi-pattern search in aligned sequences

I am currently working on a bioinformatics problem where I need to lookup and count the location and count of occurences of 4000-ish 5 character long patterns in each sequence of a fasta file of 700GB....
48 views

### Help Understanding the Greedy Motif Search Algorithm from Textbook

I am trying to go through this text book on Bioinformatics: https://www.bioinformaticsalgorithms.org. It has coding challenges and problems which I hadn't had too much trouble with until I got to the ...
86 views

### Why do we need seondary structure detection algorithms?

There are many secondary structure prediction and assignment algorithms (e.g., DSSP, STRIDE, etc.) available. On the other hand, I see that PDB files have secondary structure information available in ...
• 769
32 views

### Single Node Deletion in Cheng and Church Algorithm

Cheng and Church Algorithm is a biclustering algorithm or an unsupervised learning task with which both rows and columns in a data matrix can be placed in concurrent clusters. In the original paper, ...
1 vote
40 views

### What are the applications of Tries(data structure) of an ordered sequence of strings in bioinformatics?

This question was also asked on reddit Tries are a data structure that can be used to efficiently store and search for strings. Tries created from an ordered sequence of strings differ from the ...
• 111
96 views

### What is happening in the Zuker-Algorithm

I am trying to understand the Zuker Algorithm. What is happening during initialisation? I know in Nussinov the diagonal is filled with 0s. Are the diagonals filled with infinite energy during Zuker´s ...
44 views

### How evaluate biclustering algorithm over real datasets containing labels?

I have a set of real data containing labels. However, in some biclustering algorithms (e.g., Cheng and Church Algorithm), originally authors applied gene expression data like Yeast without having ...
53 views

### Algorithm for counting neighbors

I need an algorithm to process protein chains. The volume size would probably not exceed 30x30x30 angstrom^3. Say, I have a point cloud of 50,000 points in a 3D space. I want to count the number of ...
• 769
137 views

### Why are genetic algorithm chromosomes represented using 8 bit binary?

I am learning about genetic algorithms. Why chromosomes are represented using 8 bit binary. This arose when I apply crossover techniques to the bits. Please help me to find the answer.Thanks in ...
1 vote
80 views

### Refactoring a script mapping ID to sequence

I wrote simple Python script which has an excessive run time, notably when using large data sets. For example a data set of 1 000 000 sequences. I am seeking assistance refactoring the code and would ...
• 147
1 vote
57 views

### Improving list speed: glycosylation example

I discussed a question with @gaspanic Python/Biopython - Replace amino acid residue on MSA with "z" from a list of unaligned positions . The issue emerged was speeding up lists in Python. ...
• 12.6k
1 vote
549 views

### DNA genome string reconstruction from k-mer

I have the following quiz question, but the Pattern1 for both (ACC|ATA) and (CGA|ACT) are unique (just grep for ...
• 141
150 views

### Caching and parallelization

Currently algorithmically developing a calculation for "co-dependent" mutation (quotation appropriate). The algorithm uses chunked biopython alignment objects which are parallelized. Aim One ...
• 12.6k
16 views

### Can I use Aho-Corasick for epidemic spread simulation?

I found that with this string-finding algorithm, this algo can determine if a string(person) holds something(if he has sick, already got vaccinated, and et cetera.). I am trying to simulate an ...
1 vote
290 views

### How should I imagine the pre-indexing of suffix arrays in the STAR RNA Seq-aligner?

I'm using STAR for an internship (fusion-genes in ALL cancer) and I'd like to understand what exactly it is doing. The people at the internship don't know either how it works, given their biology ...
• 280
233 views

### Is the algorithm of the STAR RNA Seq-Aligner similar to the Knuth-Morris-Pratt string matching algorithm?

I don't know if I'm in the right SE, if not let me know and I'll delete it. I am reading the original publication of the STAR RNA-Sequence aligner. Given the quoted text below I wonder if the ...
• 280
1 vote
64 views

### What is the cutoff distance in this algorithm?

In the following article: a fast and efficient Cα-based method for accurately assigning protein secondary structure elements What are the minimum and maximum cutoff distances in this algorithm? Also,...
• 769
53 views

What does it mean by "PC" in this article? a fast and efficient Cα-based method for accurately assigning protein secondary structure elements
• 769
1 vote
455 views

### Why does randomized motif search work?

I'm looking for intuition for why a randomized motif search works. My current thinking is as follows: We are selecting many random kmers from our DNA sequences. The chosen kmers will bias the profile ...
• 127
1 vote
390 views

### Given two ADN sequence, can there be multiple optimal alignement? And how to optimally find them?

Given two sequences, I know we can determine optimal alignment of sequence with the Needleman–Wunsch algorithm. But is it possible that two alignments have multiple optimal alignment (I guess it would ...
55 views

### How to optimize the number of amplicons ordered for a PCR wet experiment with several genomic ROIs?

Imagine we have an experiment for which we would like to minimize the number of purchased primers. Let's look at the layout of a single primer below: Assume we have a precomputed set of all necessary ...
• 1,437
1 vote
149 views

### How to reconstruct a target string from a large set of overlapping reads

I got this question as a homework. Does anyone know how the it can be solved? Consider a short string $r$ as a read from a string $S$ if $r$ is converted from a substring of $S$ by at most $k$ swaps ...
• 13
189 views

### Time complexity of the Neighbors function

I implemented the following find_neighbors_with_expected_hamming_distance function that generates all k-mers of Hamming distance at most d from the given Pattern. ...
48 views

### Explaining the algorithm of RNA folding: what each symbol & value represents?

I need someone to explain to me from the nuts and bolts how algorithms/ maths is used to work out RNA folding. Explain it to me like I am an alien or child. I am looking at this paper - https://eprint....
160 views

### Why use Needleman-Wunsch if there is no way to evaluate the statistical significance

I thought that Needleman-Wunsch is the best approach to align sequences. However, I read that it is impossible to evaluate the statistical significance of the alignment if you do global alignment. So ...
• 101
1 vote
85 views

### Evaluating amateur bioinformatics results

I've might have created a new algorithm for finding patterns in DNA. The technique has not been used before, and it managed to find a 33-mer with corresponding complement that exists both in E. Coli ...
1 vote
40 views

### Kinetics "Master Equation"

In stochastic (probabilistic) models, the evolution of a system over time is calculated using a "Master Equation" which also factors the external and internal noise / perturbations in order ...
492 views

### mapping heteryzygous kmers on a genome

I have a set (a couple of millions) of kmer pairs of known length (usually 21) that I know that are heterozygous in the middle nucleotide. For instance: ...
• 5,562
113 views

### Attractor Landscape Analysis

I have come across a modeling toolbox, ATLANTIS, which is able to determine cell fates in silico based on the input models provided. This MATLAB-based toolbox is built on a method called "Attractor ...
1 vote
60 views

### How to score how densely bases are distributed along a given oligo?

Suppose I have a short chain string of oligos, and I want to rate them from 0 to 1 based on how clustered the "A"s are in respect to the chain. For example: ...
• 119
183 views

### Prediction of prokaryotic origins of replication (ORI)

I want to predict origins of replication (ORI) on hundreds of prokaryotic genomes. The most straight-forward solution would be to use most commonly used tool, Ori-Finder. It uses integrated gene ...
• 191
1 vote
108 views

### Non-random access on a fastq file

There was a nice question on random access on a fastq file, however I have the opposite problem. I want to programatically access non-random fastq entries quickly (using C++). Say I have several ...
• 3,181
179 views

### How is consensus alignment for OLC assembly usually implemented?

Background In C++ I want to implement a simple class that performs overlap layout consensus assembly but I can not figure out the most logical data structure to use for the consensus alignment step. ...
• 3,181
1 vote
72 views

### How do I interpret the function O(f^-2 log n) in Shekhar et al. (2017)?

The results of Shekhar et al. (2017) "indicate that ASTRAL requires $\mathcal{O}(f^{-2} \log{n})$ gene trees to reconstruct the species tree correctly with ...
• 21
76 views

### What are some of the major questions pursued by the field bioinformatics? [closed]

I am an occasional user of tools in bioinformatics and I am fascinated by the possibility of uncovering deeper patterns in the biological realm using the help of computer algorithms. Yet I don't know ...
195 views

### Histosketch vs Count-Min sketch: preserving similarity

A preprint describing a new tool and its application to microbiome analysis was recently published in bioRxiv[1]. At the core of this new tool, HULK, is a new data structure called a histosketch[2] ...
• 5,090
151 views

### Getting all NNI trees of a parsimony tree

I have an aligned protein sequence file which I have been using for reconstructing a parsimonious tree. I am currently using NNITreeSearcher._get_neighbors method from Biopython 1.72 but it's way to ...
• 503
658 views

### Efficiently aligning a lot of reads on the same small reference sequence

The context: I have a DNA-sequence coding for a protein, about 1500 bp in length. Using NGS, a lot of reads of (mutants of) this same sequence were acquired. All of these reads need to be aligned to ...
1 vote
36 views

### Stand alone chaining tool for existing blast hits?

I have a table of blast hits in a database that I'd like to chain. What is a good choice for a 'stand alone' chaining tool? Is it simple to implement in Perl, for example? Example 'hit' data is here. ...
• 612
90 views

### Do any computational phylogenetic methods enable the specification of ancestral states?

Various phylogenetic algorithms estimate ancestral states of a phylogenetic dataset. Is there a way in either maximum parsimony, distance-based methods, or Bayesian inference to indicate what the ...
• 317
97 views

### Why does pratchet() in phangorn not find the most parsimonious trees?

I called pratchet() on a dataset with binary values for the characters and it returned a parsimony value of 35. I then calculated the parsimony value for the ...
• 317
687 views

### How does htslib/samtools access optional BAM fields?

I am confused regarding how various software libraries deal with optional fields in a BAM: Based upon the BAM specification, there are 11 mandatory fields to a BAM: ...
• 1,423
514 views

### Books on bioinformatics algorithms

I'm looking for a book about bioinformatics algorithms, such as alignment, BLAST search, and variant calling. I'm hoping reading about this subject will give me a deeper understanding of the ...
• 189
117 views

### How does Li and Durbin's BWA paper compare alignment programs on real data?

Li and Durbin's "Fast and accurate short read alignment with burrows-whleeler transform" found here, says: We evaluate the performance of BWA on ... real paired-end data by checking the fraction ...
• 87
383 views

### How is a principal component analysis for population structure made from a bam or other alignment file?

I'm curious how a PCA for population structure is built from an alignment/BAM or SAM file. How do programs like angsd and ngsCovar actually build a PCA? What exactly makes things come out as different ...
• 87
323 views

### Estimate the length of poly-A tails from randomly-primed RNAseq data

So a poly-A tail is a long chain of adenine nucleotides that is added to a messenger RNA (mRNA) molecule during RNA processing to increase the stability of the molecule. For my project, I would like ...
• 1,691
43 views

### Large range parameter identification

I have a model (ODE) of an enzymatic reaction, and I'd like to estimate four of its parameters to fit some available data. To obtain the model I am just using Mass-Action Kinetics. Some more details: ...
• 131
1 vote
174 views

### Can structural - equation modeling be used in Bioinformatics?

I am a bioinformatics student and I was learning the basics of structural equation modeling (SEM). I was wondering, are there any applications of SEM on bioinformatics? Are there any strong sides ...
72 views

### Help with identifying disease modules [closed]

I've made an application that at this point ranks all combinations of drug pairs relevant to a biological network/graph in the order of how disruptive the outcome of deleting the targets of a given ...
• 109