Skip to main content

Questions tagged [algorithms]

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

Filter by
Sorted by
Tagged with
3 votes
2 answers
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....
Swathi Subramanyan's user avatar
5 votes
2 answers
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 ...
David Rouleau's user avatar
2 votes
1 answer
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 ...
user366312's user avatar
2 votes
1 answer
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, ...
ShokofehVS's user avatar
1 vote
1 answer
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 ...
GEP's user avatar
  • 111
0 votes
0 answers
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 ...
Serij's user avatar
  • 1
0 votes
1 answer
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 ...
ShokofehVS's user avatar
3 votes
2 answers
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 ...
user366312's user avatar
0 votes
1 answer
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 ...
Julie's user avatar
  • 1
1 vote
1 answer
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 ...
MTG's user avatar
  • 147
1 vote
2 answers
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. ...
M__'s user avatar
  • 12.6k
1 vote
0 answers
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 ...
kevin's user avatar
  • 141
2 votes
1 answer
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 ...
M__'s user avatar
  • 12.6k
0 votes
0 answers
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 ...
Dan-Ryuki's user avatar
1 vote
1 answer
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 ...
ilam engl's user avatar
  • 280
5 votes
1 answer
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 ...
ilam engl's user avatar
  • 280
1 vote
1 answer
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,...
user366312's user avatar
0 votes
1 answer
53 views

What does it mean by "PC" in this article?

What does it mean by "PC" in this article? a fast and efficient Cα-based method for accurately assigning protein secondary structure elements
user366312's user avatar
1 vote
1 answer
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 ...
Moo's user avatar
  • 127
1 vote
1 answer
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 ...
CSoverload's user avatar
3 votes
1 answer
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 ...
0x90's user avatar
  • 1,437
1 vote
1 answer
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 ...
Alex's user avatar
  • 13
0 votes
1 answer
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. ...
Deepak Tatyaji Ahire's user avatar
2 votes
0 answers
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....
confused_novice's user avatar
0 votes
1 answer
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 ...
marilu's user avatar
  • 101
1 vote
1 answer
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 ...
Beurtschipper's user avatar
1 vote
0 answers
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 ...
Osaama Shehzad's user avatar
3 votes
2 answers
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: ...
Kamil S Jaron's user avatar
4 votes
1 answer
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 ...
Osaama Shehzad's user avatar
1 vote
3 answers
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: ...
Tom's user avatar
  • 119
4 votes
1 answer
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 ...
MrTomRod's user avatar
  • 191
1 vote
1 answer
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 ...
conchoecia's user avatar
  • 3,181
2 votes
1 answer
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. ...
conchoecia's user avatar
  • 3,181
1 vote
1 answer
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 ...
Elliot's user avatar
  • 21
0 votes
1 answer
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 ...
Ahmed Abdullah's user avatar
3 votes
1 answer
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] ...
Daniel Standage's user avatar
6 votes
1 answer
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 ...
Sidra Younas's user avatar
4 votes
1 answer
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 ...
Cedric Stroobandt's user avatar
1 vote
0 answers
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. ...
Dan's user avatar
  • 612
4 votes
2 answers
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 ...
Namenlos's user avatar
  • 317
0 votes
2 answers
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 ...
Namenlos's user avatar
  • 317
7 votes
2 answers
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: ...
EB2127's user avatar
  • 1,423
8 votes
3 answers
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 ...
Ólavur's user avatar
  • 189
4 votes
2 answers
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 ...
5r9n's user avatar
  • 87
2 votes
1 answer
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 ...
5r9n's user avatar
  • 87
6 votes
2 answers
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 ...
ShanZhengYang's user avatar
3 votes
0 answers
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: ...
PepeToro's user avatar
  • 131
1 vote
2 answers
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 ...
Ugur Toprak's user avatar
5 votes
0 answers
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 ...
user1171426's user avatar
9 votes
1 answer
7k views

How are MACS2's narrow peak and broad peak algorithms different?

The peak calling tool MACS2 can call peaks in either narrow peak mode (for focused signals like transcription factor ChIPseq) or broad peak mode (for more defuse signals, like certain histone ...
Ian Sudbery's user avatar
  • 3,321