用於將多個片段中的序列拼接在一起的算法

我正在研究實時嵌入式系統。我正在嘗試創建詳細的時序分析。我收集了運行時數據，記錄了每個中斷的啓動和停止時間。數據的每個突發看起來像這樣用於將多個片段中的序列拼接在一起的算法

ISR# time 
----- ---- 
    1  34 
    end 44 
    4  74 
    3  80 
    end 93 
    end 97 
    ...

我的輸出通道的帶寬有限，而我的高精度計時器很快溢出一句話，所以我在〜150個微秒脈衝採集數據，然後滴出來一段時間。從這些數據中，我能夠收集每個中介所花費的時間以及電話和優先購買的號碼。

我想要做的是將典型框架的完整執行順序放在一起，這個框架的長度約爲2 ms。

它發生在我身上，這幾乎就像一個基因測序問題。我有幾千個片段，每個片段佔總幀數的7％。 I 應該能夠排列它們 - 匹配覆蓋幀的相同部分的部分 - 以這種方式我可以在整個週期內構建單個事件序列。會有一些幀到幀的變化，但我希望這些可以在最佳匹配類型的算法中考慮。

所以我的問題是：什麼算法存在做這種排序？有沒有針對DNA或Protiens的現有工具？

來源

2010-10-28 AShelly

追求的另一個角度是壓縮記錄，使您可以在日誌中填充10倍以上的數據。 Delta壓縮時間戳，將地址摺疊爲索引，使用可變長度的記錄，以便'結束'可以更簡潔地表達，等等。 – 2010-10-29 00:00:10

這不是一個壞主意，但它已經很好地壓縮了。每個記錄使用4位作爲ID，12位作爲時間戳。我只能通過降低定時器的分辨率來減少每個印章的位數。將其降低到14位是可能的，但這會產生自己的數據操作麻煩，通過一個16位定向的串行通道傳送它。 – AShelly 2010-10-29 17:14:48

我還沒有完全理解 - 你是否執行多次獨立運行，每個運行約2ms，其中每次捕獲約150ms？中斷的順序是開始還是停止確定性的（每次運行都一樣）還是非常接近？如果是的話，是的，就像DNA序列組裝一樣;如果沒有，我不明白你希望如何匹配它們。 – 2010-10-30 07:46:23

您的數據看起來相當具體應用，因此您可能只需要進行試驗。首先看看帶有中斷號碼的ISR調用的順序（沒有定時信息）是否充分區分;只需拿出每個突發的最後N個呼叫，並進行搜索以找到在開始附近具有類似片段的任何其他突發。您可以使用任何字符串搜索算法來完成此任務。如果返回的匹配太少，請嘗試使用模糊搜索算法。如果返回的匹配太多，請嘗試更智能的匹配算法，並根據時序的相似性對每個匹配進行加權。總體而言，這不應該太複雜，因爲一個完整的鏈只有大約15個連發，而例如在DNA測序中，您需要匹配數百萬個非常短的片段。

來源

2010-10-28 23:46:50

用於將多個片段中的序列拼接在一起的算法

回答

相關問題