Questions tagged [algorithms]
The algorithms tag has no usage guidance, but it has a tag wiki.
53 questions
1
vote
0
answers
18
views
Does anyone include *non*spliced reads in a differential splicing analysis?
AFAIK, the various tools for calculating differential splicing all calculate $\Delta\Psi$ (i.e. the change in the Percent Spliced-In). This involves examining the various relative aboundances of ...
- 401
1
vote
1
answer
61
views
How do I infer sex from a VCF file?
I have human samples VCF files that I want to infer the sex of. I do not have sequencing information or information about coverage. What's the best way to go about this? I'm looking for a robust and ...
- 637
3
votes
2
answers
82
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....
5
votes
2
answers
95
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 ...
2
votes
1
answer
90
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 ...
- 845
2
votes
1
answer
33
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, ...
- 29
1
vote
1
answer
47
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
0
votes
0
answers
104
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 ...
- 1
0
votes
1
answer
50
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 ...
- 29
3
votes
2
answers
55
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 ...
- 845
0
votes
1
answer
150
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
1
vote
1
answer
85
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
2
answers
59
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__♦
- 13k
1
vote
0
answers
614
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
2
votes
1
answer
167
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__♦
- 13k
0
votes
0
answers
17
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
1
answer
343
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
5
votes
1
answer
251
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
1
answer
69
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,...
- 845
0
votes
1
answer
56
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
- 845
1
vote
1
answer
485
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
1
answer
460
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 ...
- 11
3
votes
1
answer
58
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,447
1
vote
1
answer
156
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
0
votes
1
answer
192
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.
...
2
votes
0
answers
51
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....
1
vote
1
answer
183
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 ...
- 121
1
vote
1
answer
89
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 ...
- 113
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 ...
- 103
3
votes
2
answers
523
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,652
4
votes
1
answer
121
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 ...
- 103
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:
...
- 119
4
votes
1
answer
187
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
1
answer
111
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,201
2
votes
1
answer
187
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,201
1
vote
1
answer
76
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
0
votes
1
answer
89
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 ...
- 377
3
votes
1
answer
206
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,110
6
votes
1
answer
162
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
4
votes
1
answer
806
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
0
answers
40
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
4
votes
2
answers
91
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
0
votes
2
answers
102
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
7
votes
2
answers
722
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
9
votes
3
answers
571
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 ...
- 199
4
votes
2
answers
118
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
2
votes
1
answer
390
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
6
votes
2
answers
345
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,711
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:
...
- 131
1
vote
2
answers
178
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 ...
- 39