An Introduction to Bioinformatics Algorithms
Published 1 January 2004
Neil Jones, Pavel A. Pevzner
Citations417
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
In the early 1990s when one of us was teaching his first bioinformatics class, he was not sure that there would be enough students to teach. Although
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
Journal of Molecular BiologyBasic local alignment search tool
94,539 Citations1990Stephen F. Altschul, Warren Gish +3 more
A new approach to rapid sequence comparison, basic local alignment search tool (BLAST), directly approximates alignments that optimize a measure of local similarity, the maximal segment pair (MSP) score.
Nucleic Acids ResearchGapped BLAST and PSI-BLAST: a new generation of protein database search programs
74,499 Citations1997Stephen F. Altschul
A new criterion for triggering the extension of word hits, combined with a new heuristic for generating gapped alignments, yields a gapped BLAST program that runs at approximately three times the speed of the original.
Proceedings of the National Academy of SciencesDNA sequencing with chain-terminating inhibitors
69,306 Citations1977Frederick Sanger, S. Nicklen +1 more
A new method for determining nucleotide sequences in DNA is described, which makes use of the 2',3'-dideoxy and arabinon nucleoside analogues of the normal deoxynucleoside triphosphates, which act as specific chain-terminating inhibitors of DNA polymerase.
Molecular Biology and EvolutionThe neighbor-joining method: a new method for reconstructing phylogenetic trees.
60,481 Citations1987Naruya Saitou, M Nei
The neighbor-joining method and Sattath and Tversky's method are shown to be generally better than the other methods for reconstructing phylogenetic trees from evolutionary distance data.
The Journal of Chemical PhysicsEquation of State Calculations by Fast Computing Machines
37,074 Citations1953N. Metropolis, Arianna W. Rosenbluth +3 more
Proceedings of the National Academy of SciencesCluster analysis and display of genome-wide expression patterns
16,395 Citations1998Michael B. Eisen, Paul T. Spellman +2 more
A system of cluster analysis for genome-wide expression data from DNA microarray hybridization is described that uses standard statistical algorithms to arrange genes according to similarity in pattern of gene expression, finding in the budding yeast Saccharomyces cerevisiae that clustering gene expression data groups together efficiently genes of known similar function.
IEEE Transactions on Information TheoryLeast squares quantization in PCM
15,578 Citations1982Sheelagh Lloyd
The corresponding result for any finite number of quanta is derived; that is, necessary conditions are found that the quanta and associated quantization intervals of an optimum finite quantization scheme must satisfy.
Journal of Molecular BiologyA general method applicable to the search for similarities in the amino acid sequence of two proteins
11,464 Citations1970Saul B. Needleman, Christian D. Wunsch
A computer adaptable method for finding similarities in the amino acid sequences of two proteins has been developed and it is possible to determine whether significant homology exists between the proteins to trace their possible evolutionary development.
Journal of Molecular BiologyIdentification of common molecular subsequences
10,081 Citations1981Temple F. Smith, Michael S. Waterman
This letter extends the heuristic homology algorithm of Needleman & Wunsch (1970) to find a pair of segments, one from each of two long sequences, such that there is no other Pair of segments with greater similarity (homology).
Proceedings of the National Academy of SciencesA new method for sequencing DNA.
7,969 Citations1977Allan M. Maxam, Wendy V. Gilbert
Reactions that cleave DNA preferentially at guanines, at adenines,At cytosines and thymines equally, and at cytosine alone are described.
Journal of the American Society for Mass SpectrometryAn approach to correlate tandem mass spectral data of peptides with amino acid sequences in a protein database
6,626 Citations1994Jimmy K. Eng, Ashley L. McCormack +1 more
The approach described in this manuscript provides a convenient method to interpret tandem mass spectra with known sequences in a protein database.
Systematic BiologyToward Defining the Course of Evolution: Minimum Change for a Specific Tree Topology
6,512 Citations1971W. M. Fitch
A method is presented that is asserted to provide all hypothetical ancestral character states that are consistent with describing the descent of the present-day character states in a minimum number of changes of state using a predetermined phylogenetic relationship among the taxa represented.
The complexity of theorem-proving procedures
6,107 Citations1971Stephen Cook
It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology.
Biodiversity Heritage Library (Smithsonian Institution)A Statistical Method for Evaluating Systematic Relationships
4,490 Citations1958Robert R. Sokal, Charles D. Michener
Journal of Molecular BiologyPrediction of complete gene structures in human genomic DNA
4,264 Citations1997Chris Burge, Samuel Karlin
A general probabilistic model of the gene structure of human genomic sequences which incorporates descriptions of the basic transcriptional, translational and splicing signals, as well as length distributions and compositional features of exons, introns and intergenic regions is introduced.
ScienceRapid and Sensitive Protein Similarity Searches
4,090 Citations1985David J. Lipman, William R. Pearson
An algorithm was developed which facilitates the search for similarities between newly determined amino acid sequences and sequences already available in databases and increases sensitivity by giving high scores to those amino acid replacements which occur frequently in evolution.
SIAM Journal on ComputingFast Pattern Matching in Strings
2,917 Citations1977Donald E. Knuth, James H. Morris +1 more
An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings, showing that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time.
Nucleic Acids ResearchREPuter: the manifold applications of repeat analysis on a genomic scale
2,794 Citations2001Stefan Kurtz
The wide scope of repeat analysis is circumscribes using applications in five different areas of sequence analysis: checking fragment assemblies, searching for low copy repeats, finding unique sequences, comparing gene structures and mapping of cDNA/EST sequences.
ScienceLight-Directed, Spatially Addressable Parallel Chemical Synthesis
2,691 Citations1991Stephen P. A. Fodor, Jill Read +4 more
High-density arrays formed by light-directed synthesis are potentially rich sources of chemical diversity for discovering new ligands that bind to biological receptors and for elucidating principles governing molecular interactions.
Communications of the ACMA fast string searching algorithm
2,292 Citations1977Robert S. Boyer, J Strother Moore
The algorithm has the unusual property that, in most cases, not all of the first i.” in another string, are inspected.
Series on software engineering and knowledge engineeringData Structures and Algorithms
2,131 Citations2003
The basis of this book is the material contained in the first six chapters of the earlier work, The Design and Analysis of Computer Algorithms, and has added material on algorithms for external storage and memory management.
Journal of Molecular BiologyHidden Markov Models in Computational Biology
1,961 Citations1994Anders Krogh, Michael Brown +3 more
The results suggest the presence of an EF-hand calcium binding motif in a highly conserved and evolutionary preserved putative intracellular region of 155 residues in the alpha-1 subunit of L-type calcium channels which play an important role in excitation-contraction coupling.
Journal of Molecular EvolutionProgressive sequence alignment as a prerequisitetto correct phylogenetic trees
1,904 Citations1987Da-Fei Feng, Russell F. Doolittle
A progressive alignment method that utilizes the Needleman and Wunsch pairwise alignment algorithm iteratively to achieve the multiple alignment of a set of protein sequences and to construct an evolutionary tree depicting their relationship is described.
ScienceDetecting Subtle Sequence Signals: a Gibbs Sampling Strategy for Multiple Alignment
1,825 Citations1993Charles E. Lawrence, Stephen F. Altschul +4 more
A mathematical definition of this "local multiple alignment" problem suitable for full computer automation has been used to develop a new and sensitive algorithm, based on the statistical method of iterative sampling, that finds an optimized local alignment model for N sequences in N-linear time, requiring only seconds on current workstations.
Linear pattern matching algorithms
1,810 Citations1973Peter Weiner
A linear time algorithm for obtaining a compacted version of a bi-tree associated with a given string is presented and indicated how to solve several pattern matching problems, including some from [4] in linear time.
Journal of Molecular BiologyAn improved algorithm for matching biological sequences
1,739 Citations1982Osamu Gotoh
The algorithm of Waterman et al. (1976) for matching biological sequences was modified under some limitations to be accomplished in essentially MN steps, instead of the M 2 N steps necessary in the original algorithm.
Algorithms on strings, trees, and sequences
1,723 Citations1997Dan Gusfield
Methods in enzymology on CD-ROM/Methods in enzymology[22] Using CLUSTAL for multiple sequence alignments
1,572 Citations1996Desmond G. Higgins, Julie Thompson +1 more
It is argued that using one weight matrix and two gap penalties is too simplistic to be of general use in the most difficult cases and a large number of new parameters designed primarily to help encourage gaps in loop regions are replaced.
Proceedings of the National Academy of SciencesMethods for assessing the statistical significance of molecular sequence features by using general scoring schemes.
1,560 Citations1990Samuel Karlin, Stephen F. Altschul
Using an appropriate random model, this work presents a theory that provides precise numerical formulas for assessing the statistical significance of any region with high aggregate score and examples are given of applications to a variety of protein sequences, highlighting segments with unusual biological features.
ScienceSimian Sarcoma Virus <i>onc</i> Gene, v- <i>sis</i> , Is Derived from the Gene (or Genes) Encoding a Platelet-Derived Growth Factor
1,549 Citations1983Russell F. Doolittle, Michael W. Hunkapiller +5 more
The demonstrating of extensive sequence similarity between the transforming protein derived from the simian sarcoma virus onc gene, v-sis, and a human platelet-derived growth factor shows that this protein could be a factor active transiently during normal cell growth.
Analytical ChemistryError-Tolerant Identification of Peptides in Sequence Databases by Peptide Sequence Tags
1,469 Citations1994Matthias Mann, Matthias Wilm
A new approach to the identification of mass spectrometrically fragmented peptides is demonstrated and an algorithm developed here that uses the sequence tag to find the peptide in a sequence database is up to 1 million-fold more discriminating than the partial sequence information alone.
Proceedings of the National Academy of SciencesSpliced segments at the 5′ terminus of adenovirus 2 late mRNA
1,375 Citations1977Susan M. Berget, Claire Moore +1 more
Four segments of viral RNA may be joined together during the synthesis of mature hexon mRNA, a model is presented for adenovirus late mRNA synthesis that involves multiple splicing during maturation of a larger precursor nuclear RNA.
Proceedings of the National Academy of SciencesProfile analysis: detection of distantly related proteins.
1,339 Citations1987Michael Gribskov, A. McLachlan +1 more
Tests with globin and immunoglobulin sequences show that profile analysis can distinguish all members of these families from all other sequences in a database containing 3800 protein sequences.
IBM Journal of Research and DevelopmentEfficient randomized pattern-matching algorithms
1,277 Citations1987Richard M. Karp, Michael O. Rabin
BioinformaticsIdentifying DNA and protein patterns with statistically significant alignments of multiple sequences.
1,269 Citations1999Gerald Z. Hertz, Gary D. Stormo
A greedy algorithm for determining alignments of functionally related sequences is described, and the accuracy of the P value calculations are tested, and an example of using the algorithm to identify binding sites for the Escherichia coli CRP protein is given.
Analytical ChemistryMethod to Correlate Tandem Mass Spectra of Modified Peptides to Amino Acid Sequences in the Protein Database
1,257 Citations1995John R. Yates, Jimmy K. Eng +2 more
The approach described in this paper provides a convenient method to match the nascent tandem mass spectra of modified peptides to sequences in a protein database and thereby identify previously unknown sites of modification.
Computer applications in the biosciencesOptimal alignments in linear space
1,245 Citations1988Eugene W. Myers, Webb Miller
The goal of this paper is to give Hirschberg's idea the visibility it deserves by developing a linear-space version of Gotoh's algorithm, which accommodates affine gap penalties.
Proteins Structure Function and BioinformaticsPfam: A comprehensive database of protein domain families based on seed alignments
1,236 Citations1997Erik L. L. Sonnhammer, Sean R. Eddy +1 more
A database based on hidden Markov model profiles (HMMs), which combines high quality and completeness, and a large number of previously unannotated proteins from the Caenorhabditis elegans genome project were classified.
Journal of Computational BiologyClustering Gene Expression Patterns
1,229 Citations1999Amir Ben‐Dor, Ron Shamir +1 more
CellAn amazing sequence arrangement at the 5′ ends of adenovirus 2 messenger RNA
1,196 Citations1977Louise T. Chow, Richard Gelinas +2 more
Findings imply a new mechanism for the biosynthesis of Ad2 mRNA in mammalian cells which is complementary to sequences within the Ad2 genome which are remote from the DNA from which the main coding sequence of each mRNA is transcribed.
Communications of the ACMA linear space algorithm for computing maximal common subsequences
1,108 Citations1975D. S. Hirschberg
The problem of finding a longest common subsequence of two strings has been solved in quadratic time and space and an algorithm is presented which will solve this problem in QuadraticTime and in linear space.
Bioinformatics the machine learning approach
929 Citations1998Pierre Baldi, Søren Brunak
Choice Reviews OnlineBioinformatics: sequence and genome analysis
767 Citations2001
The aim of this book is to provide a grounding in probability and statistical analysis of sequence alignments, as well as a jumping-off point for future research into bioinformatics programming.
Nucleic Acids ResearchUse of the ‘Perceptron’ algorithm to distinguish translational initiation sites in<i>E. coli</i>
669 Citations1982Gary D. Stormo, Thomas D. Schneider +2 more
A "Perceptron" algorithm is used to find a weighting function which distinguishes E. coli translational initiation sites from all other sites in a library of over 78,000 nucleotides of mRNA sequence.
Journal of Computer and System SciencesA faster algorithm computing string edit distances
654 Citations1980William Joseph Masek, Michael S. Paterson
An algorithm is described for computing the edit distance between two strings of length n and m, n ⪖ m, which requires O(n · max(1, mlog n) steps whenever the costs of edit operations are integral multiples of a single positive real number and the alphabet for the strings is finite.
NatureOut of Africa again and again
617 Citations2002Alan R. Templeton
A coherent picture of recent human evolution emerges with two major themes: first is the dominant role that Africa has played in shaping the modern human gene pool through at least two—not one—major expansions after the original range extension of Homo erectus out of Africa, and second is the ubiquity of genetic interchange between human populations.
Proceedings of the National Academy of SciencesLengths of chromosomal segments conserved since divergence of man and mouse.
605 Citations1984Joseph H. Nadeau, Brian Taylor
Evidence is presented suggesting that chromosomal rearrangements that determine the lengths of these segments are randomly distributed within the genome.
Journal of Molecular BiologyA restriction enzyme from Hemophilus influenzae
599 Citations1970Thomas J. Kelly, Hamilton O. Smith
Journal of Computational Biology<i>De Novo</i> Peptide Sequencing via Tandem Mass Spectrometry
597 Citations1999Vlado Dančík, Theresa A. Addona +3 more
A new algorithm, SHERENGA, is developed for de novo interpretation of MS/MS spectral interpretation that automatically learns fragment ion types and intensity thresholds from a collection of test spectra generated from any type of mass spectrometer.
SIAM Journal on Applied MathematicsMinimal Mutation Trees of Sequences
591 Citations1975David Sankoff
Proceedings of the National Academy of SciencesHidden Markov models of biological primary sequence information.
458 Citations1994Pierre Baldi, Yves Chauvin +2 more
A smooth and convergent algorithm is introduced to iteratively adapt the transition and emission parameters of the models from the examples in a given family, yielding an effective multiple-alignment algorithm which requires O(KN2) operations, linear in the number of sequences.
Bioinformatics : a practical guide to the analysis of genes andproteins
417 Citations1998Andreas D. Baxevanis, B. F. Francis Ouellette
Genome ResearchGenome Rearrangements in Mammalian Evolution: Lessons From Human and Mouse Genomes
387 Citations2002Pavel A. Pevzner, Glenn Tesler
A new algorithm for constructing synteny blocks is described, arrangements of Synteny blocks in human and mouse are studied, a most parsimonious human-mouse rearrangement scenario is derived, and evidence that intrachromosomal rearrangements are more frequent than interchromosomal restructures is provided.
Journal of Molecular BiologyStudies of Simian virus 40 DNA
373 Citations1973Kathleen J. Danna, George H. Sack +1 more
A physical map of the Simian virus 40 genome has been constructed on the basis of specific cleavage of Simianirus 40 DNA by bacterial restriction endonucleases and the single site in SV40 DNA cleaved by the Escherichia coli RI restrictions endonuclease has been located.
Computer applications in the biosciencesIdentification of consensus patterns in unaligned DNA sequences known to be functionally related
356 Citations1990Gerald Z. Hertz, George Hartzell +1 more
A method for identifying consensus patterns in a set of unaligned DNA sequences known to bind a common protein or to have some other common biochemical function is developed, based on a matrix representation of binding site patterns.
GenomicsSequencing of megabase plus DNA by hybridization: Theory of the method
353 Citations1989Radoje Dramanac, Ivan Labat +2 more
Estimates of the types and numbers of oligonucleotides that would have to be synthesized in order to sequence a megabase plus segment of DNA have been used to show advantages over existing methods because of the inherent redundancy and parallelism in its data gathering.
BioinformaticsFinding composite regulatory patterns in DNA sequences
335 Citations2002Eleazar Eskin, Pavel A. Pevzner
This paper presents a MITRA (MIsmatch TRee Algorithm) approach for discovering composite signals and demonstrates that MITRA performs well for both monad and composite patterns by presenting experiments over biological and synthetic data.
Proceedings of the National Academy of SciencesGene recognition via spliced sequence alignment.
310 Citations1996Mikhail S. Gelfand, Andrey A. Mironov +1 more
A spliced alignment algorithm and software tool that explores all possible exon assemblies in polynomial time and finds the multiexon structure with the best fit to a related protein.
Discrete MathematicsBounds for sorting by prefix reversal
298 Citations1979William H. Gates, Christos H. Papadimitriou
It is shown that @?(n)= =17n16 for n a multiple of 16 and if each integer is required to participate in an even number of reversed prefixes, the corresponding function g(n) is shown to obey 3n2-1=.
Journal of Molecular BiologyA new algorithm for best subsequence alignments with application to tRNA-rRNA comparisons
294 Citations1987Michael S. Waterman, Mark Eggert
The algorithm of Smith & Waterman for identification of maximally similar subsequence is extended to allow identification of all non-intersecting similar subsequences with similarity score at or above some preset level to be applied to comparisons of tRNA-rRNA sequences from Escherichia coli.
Journal of Biomolecular Structure and Dynamicsl-Tuple DNA Sequencing: Computer Analysis
290 Citations1989Pavel A. Pevzner
It is shown that the biochemical problems connected with the loss of information about the l-tuple DNA composition during hybridization are not crucial and can be overcome by finding the maximal flow of minimal cost in the special graph.
Journal of Computational BiologyAlgorithms for Extracting Structured Motifs Using a Suffix Tree with an Application to Promoter and Regulatory Site Consensus Identification
247 Citations2000Laurent Marsan, Marie-France Sagot
Two exact algorithms for extracting conserved structured motifs from a set of DNA sequences are introduced and are efficient enough to be able to infer site consensi, such as promoter sequences or regulatory sites, from aSet of unaligned sequences corresponding to the noncoding regions upstream from all genes of a genome.
AlgorithmicaCombinatorial algorithms for DNA sequence assembly
237 Citations1995John Kececioglu, Eugene W. Myers
A four-phase approach based on rigorous design criteria is presented, and has been found to be very accurate in practice and can accommodate high sequencing error rates.
Journal of Molecular BiologyIdentification of Protein Coding Regions In Genomic DNA
234 Citations1995Eric E. Snyder, Gary D. Stormo
A computer program, GeneParser, which identifies and determines the fine structure of protein genes in genomic DNA sequences and can rapidly generate ranked suboptimal solutions, each of which is the optimum solution containing a given intron-exon junction is developed.
Journal of Combinatorial Theory Series BComparison of labeled trees with valency three
233 Citations1971D. F. Robinson
Proceedings of the National Academy of SciencesInversions in the Third Chromosome of Wild Races of Drosophila Pseudoobscura, and Their Use in the Study of the History of the Species
211 Citations1936A. H. Sturtevant, Th. Dobzhansky
So far the authors have found at least fourteen different gene-sequences in wild stocks, and have found that in most geographical regions several sequences are present, though no single sequence appears to occur throughout the range of the species.
Finding motifs using random projections
166 Citations2001Jeremy Buhler, Martin Tompa
A novel motif discovery algorithm based on the use of random projections of the input's substrings is introduced that performs better than existing algorithms and typically solves the difficult (14,4)-, (16,5)-, and (18,6)-motif problems quite efficiently.
Lecture notes in computer science1.375-Approximation Algorithm for Sorting by Reversals
152 Citations2002Piotr Berman, Sridhar Hannenhalli +1 more
By exploiting the polynomial time algorithm for sorting signed permutations and by developing a new approximation algorithm for maximum cycle decomposition of breakpoint graphs, a new 1.375-algorithm for the MIN-SBR problem is designed.
Journal of Computational BiologyMutation-Tolerant Protein Identification by Mass Spectrometry
143 Citations2000Pavel A. Pevzner, Vlado Dančík +1 more
A new notion of spectral similarity is introduced that allows one to identify related spectra even if the corresponding peptides have multiple modifications/mutations, and a new algorithm for mutation-tolerant database search as well as a method for cross-correlating related uncharacterized spectra.
Lecture notes in computer scienceEdit distance for genome comparison based on non-local operations
133 Citations1992David Sankoff
A number of measures of gene order rearrangement are defined, algorithm design and software development for the calculation of some of these quantities in single-chromosome genomes are described, and the results of applying these tools to a database of mitochondrial gene orders inferred from genomic sequences are reported on.
GenomicsPairwise end sequencing: a unified approach to genomic mapping and sequencing
123 Citations1995Jared C. Roach, Cecilie Boysen +2 more
This work simulates and analyzes the parameters of pairwise sequencing projects including template length, sequence read length, and total sequence redundancy and finds that pairwise strategies are effective with both small (cosmid) and large (megaYAC) targets and produce ordered sequence data with a high level of mapping completeness.
Nucleic Acids ResearchSEQAID: a DNA sequence assembling program based on a mathematical model
106 Citations1984Hannu Peltola, Hans Söderlund +1 more
A program package, called SEQAID, to support DNA sequencing is presented that automatically assembles long DNA sequences from short fragments with minimal user interaction and implements several new well-behaved algorithms based on a mathematical model of the problem.
Journal of Biological ChemistryGlutaredoxin from Rabbit Bone Marrow
103 Citations1989Sarah Hopper, Richard S. Johnson +2 more
Rabbit glutaredoxin strongly resembles the corresponding calf and pig proteins (known as glutared toxin and thiol transferase, respectively) with respect to its primary structure and enzymatic activity as a GSH:disulfide thioltransferase, an activity also found for the glutaringoxin from Escherichia coli.
Algorithms and combinatoricsReconstructing Sets From Interpoint Distances
97 Citations2003Paul Lemke, Steven Skiena +1 more
This work is interested in the algorithmic problem of determining such point sets for a given collection of distances and the combinatorial problem of finding bounds on the maximum number of different solutions.
Protein modeling using hidden Markov models: analysis of globins
92 Citations2002David Haussler, Anders Krogh +2 more
A variant of the expectation maximization algorithm known as the Viterbi algorithm is used to obtain the statistical model from the unaligned sequences, and a multiple alignment of the 400 sequences and 225 other globin sequences was obtained that agrees almost perfectly with a structural alignment by D Bashford et al. (1987).
AlgorithmicaMultiple filtration and approximate pattern matching
87 Citations1995Pavel A. Pevzner, Michael S. Waterman
This paper describes a two-stage process that uses a new technique to preselect roughly similarm-tuples and demonstrates the advantages of multiple filtration in comparison with other techniques for approximate pattern matching.
Efficient string matching in the presence of errors
76 Citations1985Gad M. Landau, Uzi Vishkin
An algorithm for finding all occurrences of the pattern in the text, each with at most k mismatches (superfluous characters in either the text or the pattern are not allowed), which runs in O(k(m logm + n)) time.
Journal of Computational BiologyAn Exponential Example for a Partial Digest Mapping Algorithm
36 Citations1994Zheng Zhang
This paper presents an exponential example for a simple backtracking algorithm of Skiena et al. that works well in practice and raises the question whether anonential example exists for this algorithm.
Nucleic Acids ResearchRegulatory pattern Identification in nucleic acid sequences
34 Citations1983John R. Sadler, Michael S. Waterman +1 more
A critique of the often employed consensus and local homology methods suggests the need for new tools to use the positional and structural data now becoming available on exactly what it is that is recognized in the DNA sequence by sequence-specific binding proteins.
Theoretical Computer ScienceThe chords’ problem
16 Citations2002Alain Daurat, Yan Gérard +1 more
This paper provides, in dimension 1, two different algorithms to reconstruct the set of points according to their chords’ multiset, the first one is given for its effectiveness in spite of an uncertain complexity whereas the second one is the first polynomial algorithm solving the chords' problem.
…