Approximating the expected number of inversions given the number of breakpoints
2002 (English)In: Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349, Vol. 2452, 316-330 p.Article in journal (Refereed) Published
We look at a problem with motivation from computational biology: Given the number of breakpoints in a permutation (representing a gene sequence), compute the expected number of inversions that have occured. For this problem, we obtain an analytic approximation that is correct within a percent or two. For the inverse problem, computing the expected number of breakpoints after any number of inversions, we obtain an analytic approximation with an error of less than a hundredth of a breakpoint.
Place, publisher, year, edition, pages
Berlin, Germany: Springer Berlin/Heidelberg, 2002. Vol. 2452, 316-330 p.
Mathematics Discrete Mathematics
IdentifiersURN: urn:nbn:se:oru:diva-41723ISI: 000187294100024ISBN: 3-540-44211-1OAI: oai:DiVA.org:oru-41723DiVA: diva2:781039
2nd International workshop on Algorithms in Bioinformatics, WABI 2002, Rome, Italy, Sep. 17-21, 2002